有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。求走完这个台阶一共有多少种走法。
要分析这个问题，我们先找一个台阶看看
不好意思，不是这种台阶，重新找一个
假设只剩最后一步就走到第10级台阶，这时会出现几种情况？
第一种情况：从位置A，跨1级台阶到终点
第一种情况：从位置B，跨2级台阶到终点
F(10) = F(9) + F(8)
F(9) = F(8) + F(7)
...
F(3) = F(2) + F(1)
F(2) = 2
F(1) = 1
F(n) = F(n-1) + F(n-2) (n≥3)
// 递归实现方式
function getClimbingWays (n) {
if (n < 1) return 0;
if (n === 1) return 1;
if (n === 2) return 2;
return getClimbingWays(n-1) + getClimbingWays(n-2);
}
递归实现方式的时间复杂度分析
要计算原问题 F(10)，就需要先计算出子问题 F(9) 和 F(8)
然后要计算 F(9)，又要先算出子问题 F(8) 和 F(7)，以此类推。
一直到 F(2) 和 F(1），递归树才终止
递归时间复杂度 = 解决一个子问题时间 * 子问题个数
- 一个子问题时间 = F(n-1)+ F(n-2)，也就是一个加法的操作，所以复杂度是 O(1)；
- 问题个数 = 递归树节点的总数，递归树的总节点 = 2^n-1， 所以是复杂度O(2^n)。
- 所以递归实现方式的时间复杂度 = O(1) * O(2^n) = O(2^n)，指数级别的，存在性能问题。
仔细观察这颗递归树，你会发现存在大量重复计算，比如F(n-2)被计算了两次，F(n-3)被重复计算了3次...所以这个递归算法低效的原因，就是存在大量的重复计算！
// 递归 + 备忘录
function getClimbingWays (n) {
const dataMap = new Map();
if (n < 1) return 0;
if (n === 1) return 1;
if (n === 2) return 2;
if (dataMap.has(n)) {
return dataMap.get(n);
} else {
const val = getClimbingWays(n-1) + getClimbingWays(n-2);
dataMap.set(n, val);
return val;
}
}
带备忘录的递归的复杂度分析
- 一个子问题时间 = F(n-1)+ F(n-2)，也就是一个加法的操作，所以复杂度是 O(1)；
- 问题个数 = 1 ~ n个， 所以是复杂度O(n)。
- 所以带备忘录的递归的时间复杂度 = O(1) * O(n) = O(n)。
- dataMap中存了n-2个节点，所以它的空间复杂度是O(n)。
至此，算法写出来了，性能也优化了，但这还不是真正的动态规划的实现(っ°Д°;)っ
- 带备忘录的递归，是从F(10)往F(1）方向延伸求解的，所以也称为自顶向下的解法。
- 动态规划从较小问题的解，由交叠性质，逐步决策出较大问题的解，它是从F(1)往F(10）方向，往上推求解，所以称为自底向上的解法。
动态规划有几个典型特征，在台阶问题中：
F(9) 和F(8)是F(10)的 最优子结构
F(1)、F(2)被称为问题的边界，如果一个问题没有边界，将无法得出有限的结果
F(n) = F(n-1) + F(n-2) 是阶段之间的状态转移方程
// 动态规划
function getClimbingWays (n) {
if (n < 1) return 0;
if (n === 1) return 1;
if (n === 2) return 2;
let a = 1;
let b = 2;
let sum = 0;
for (let i = 3; i <= n; i++ ) {
sum = a + b;
a = b;
b = sum;
}
return sum;
}
算法复杂度分析
进行了一层循环，时间复杂度为O(n)。
F(n)只依赖前面两个数，所以只需要三个变量a、b和sum来存储，因此空间复杂度是O(1)。
扩展一下，二维数组的动态规划
一个机器人位于一个 m x n 网格的左上角(m和n均不超过100), 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？
https://leetcode-cn.com/problems/unique-paths/
1.定义数组元素的含义
定义 dp[i][j]的含义为：当机器人从左上角走到(i, j) 这个位置时，一共有 dp[i][j] 种路径。那么，dp[m-1] [n-1] 就是我们要的答案了（数组下标从0开始）。
2.找出关系数组元素间的关系式
由于机器人可以向下走或者向右走，所以有两种方式, 一种是从 (i-1, j) 这个位置向下走一步到达，
一种是从(i, j - 1) 这个位置向右走一步到达。
得出关系式： dp[i][j] = dp[i-1][j] + dp[i][j-1]
3.找出初始值
显然，当 dp[i][j] 中，如果 i 或者 j 有一个为 0，那就只有一种走法。
dp[0][0….n-1] = 1; // 相当于最上面一行，机器人只能一直往右走
dp[0…m-1][0] = 1; // 相当于最左面一列，机器人只能一直往下走
function uniquePaths (m, n) {
if (m <=0 || n <= 0) return 0;
// 初始化二维数组
const dp = new Array(n);
for (let i = 0;i < n; i++) {
dp[i] = new Array(m);
}
// 初始化边界值
for (let i = 0; i < m; i++) {
dp[0][i] = 1;
}
for (let j = 0; j < n; j++) {
dp[j][0] = 1;
}
// 按关系式计算并填充数组的值
for (let i = 1; i < n; i++) {
for (let j = 1; j < m; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[n-1][m-1];
};
算法复杂度分析
进行了两层循环，时间复杂度为O(n*m)。
使用一个二维数组存储数据，空间复杂度也是O(n*m)
