动态规划与贪心的不同：
动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。
动态规划的解题步骤：
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
动态规划的常见题目：
- 背包问题
- 打家劫舍
- 股票问题
- 子序列问题
1. 斐波那契数
递归
var fib = function(n) {
if(n <= 1) return n;
return fib(n - 1) + fib(n - 2);
};
时间复杂度：O(2^n)
空间复杂度：O(n)
动规
动规五部曲;
-
确定dp数组（dp table）以及下标的含义
dp[i]的定义为：第i个数的斐波那契数值是dp[i] -
确定递推公式
状态转移方程
dp[i] = dp[i - 1] + dp[i - 2];
-
dp数组如何初始化
dp[0] = 1, dp[1] = 1;
-
确定遍历顺序
由于
dp[i]
是依赖于
dp[i - 1]
和
dp[i - 2]
的，所以遍历顺序是从前向后 -
举例推导dp数组
如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。
var fib = function(n) {
let dp = [];
dp[0] = 0, dp[1] = 1;
for(let i = 2; i <= n; i++) {
dp[i] = dp[i- 1] + dp[i - 2];
}
return dp[n];
};
时间复杂度：O(n)
空间复杂度：O(n)
优化：其实我们只需要维护两个数值就行了，不需要记录整个序列。
var fib = function(n) {
if(n <= 1) return n;
let p = 0, q = 1;
for(let i = 2; i <= n; i++) {
let sum = p + q;
p = q;
q = sum;
}
return q;
};
时间复杂度：O(n)
空间复杂度：O(1)
2. 爬楼梯
动规五部曲;
-
确定dp数组（dp table）以及下标的含义
dp[i]的定义为：爬到第i层楼梯，有dp[i]种方法 -
确定递推公式
状态转移方程
dp[i] = dp[i - 1] + dp[i - 2];
-
dp数组如何初始化
dp[1] = 1, dp[2] = 2;
-
确定遍历顺序
由于
dp[i]
是依赖于
dp[i - 1]
和
dp[i - 2]
的，所以遍历顺序是从前向后 -
举例推导dp数组
如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。
版本一
var climbStairs = function(n) {
let dp = [1, 2];
for(let i = 2; i < n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n - 1];
};
版本二
var climbStairs = function(n) {
let p = 0, q = 0, r = 1;
for (let i = 1; i <= n; ++i) {
p = q;
q = r;
r = p + q;
}
return r;
};
拓展：一步一个台阶，两个台阶，三个台阶，直到 m个台阶，有多少种方法爬到n阶楼顶？
3. 使用最小花费爬楼梯
动规五部曲;
-
确定dp数组（dp table）以及下标的含义
dp[i]的定义为：爬到第i层楼梯的最小花费 -
确定递推公式
有两个途径到达第i层楼梯，可以从
i - 1
或
i - 2
层楼梯上去。
状态转移方程
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
-
dp数组如何初始化
dp[0] = 0, dp[1] = 0;
-
确定遍历顺序
由于
dp[i]
是依赖于
dp[i - 1]
和
dp[i - 2]
的，所以遍历顺序是从前向后 -
举例推导dp数组
如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。
var minCostClimbingStairs = function(cost) {
let dp = [];
dp[0] = 0, dp[1] = 0;
for(let i = 2; i <= cost.length; i++) {
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[dp.length - 1];
};
4. 不同路径
深搜
思路：机器人每次只能向下或者向右移动一步，那么其实机器人走过的路径可以抽象为一棵二叉树，而叶子节点就是终点。
时间复杂度为O(2^(m + n – 1) – 1)，指数级别。
动规
动规五部曲;
-
确定dp数组（dp table）以及下标的含义
dp[i][j]的定义为：机器人到达(i, j)位置时有 dp[i][j] 条不同路径数 -
确定递推公式
有两个途径到达(i, j)位置，可以从(i – 1, j)位置向下移动一步或(i, j – 1)位置向右移动一步。
状态转移方程
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
误区：从
dp[i - 1][j]
到
dp[i][j]
，路径数加一。从
dp[i - 1][j]
到
dp[i][j]
，只能向下走一步，所以路径数是不变得。
dp[i][j - 1]
同理。
-
dp数组如何初始化
dp[0][j] = 1, dp[i][0] = 1;
-
确定遍历顺序
遍历顺序是从上向下以及从左向右。
var uniquePaths = function(m, n) {
let dp = new Array(m).fill(1).map(() => new Array(n).fill(1));
// for(let i = 0; i < m; i++) dp[i][0] = 1;
// for(let j = 0; j < n; j++) dp[0][j] = 1;
for(let i = 1; i < m; i++) {
for(let j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
};
时间复杂度：O(m × n)
空间复杂度：O(m × n)
数论
在这个图中，可以看出一共m，n的话，无论怎么走，走到终点都需要 m + n – 2 步。其中一定有 m – 1 步是要向下走的，不用管什么时候向下走。问题转化为组合问题，
给你m + n – 2个不同的数，随便取m – 1个数，有几种取法。
时间复杂度：O(m)
空间复杂度：O(1)
5. 不同路径 II
与上题不同之处：当(i, j)为0时，也就是没有障碍时才进行递归。初始化不同，在首行/首列遇到障碍物就直接退出for循环了。
var uniquePathsWithObstacles = function(obstacleGrid) {
let m = obstacleGrid.length, n = obstacleGrid[0].length;
let dp = new Array(m).fill(0).map(() => new Array(n).fill(0));
for(let i = 0; i < m && obstacleGrid[i][0] === 0; i++) dp[i][0] = 1;
for(let j = 0; j < n && obstacleGrid[0][j] === 0; j++) dp[0][j] = 1;
for(let i = 1; i < m; i++) {
for(let j = 1; j < n; j++) {
if(obstacleGrid[i][j] === 0) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
};