动态规划与递归
动态规划的思想和递归的思想类似，都是把复杂问题分解成若干小问题来求解。不同的是动态规划解决了重复求解的问题，递归中可能存在重复求解子问题。
比如最简单的兔子数列问题：
// 递归
function fib(n) {
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
当 n == 4 求解fib(4) = fib(3) + fib(2) 进一步转化 fib(4) = fib(2) + fib(1) + fib(2)
这中间就出现了两次fib(2)，这个fib(2)就是重复的子问题，这个递归写法当n变得很大的时候就会出现非常多的重复计算的子问题，计算会非常的耗时。
当然这里可以用尾递归调用或者记忆化递归的方式来优化
// 动态规划
function fib(n) {
let dp = [0, 1];
for (let i = 2; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
不过上面的动态规划还有可以优化的点，因为求解的第三项等于前两项的和，不需要存储所有的项，只需要求解的项和它的前两项，所以可以修改为
function fib(n) {
let dp = [0, 1, 1];
for (let i = 2; i < n; ++i) {
dp[0] = dp[1];
dp[1] = dp[2];
dp[2] = dp[1] + dp[0];
}
return dp[2];
}
动态规划求解套路
首先，利用动态规划求解，需要分析出dp[i]或者复杂一点的dp[i][j]代表什么
然后分析出状态转移方程也就是像dp[i] = dp[i - 1] + dp[i - 2]这样的关系
再其次分析dp的初始值和边界情况。比如上面的
// 动态规划
function fib(n) {
// 0, 1初始值
let dp = [0, 1];
// i - 2不能小于0，即为边界条件
for (let i = 2; i <= n; ++i) {
// 状态转移方程
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
一个常见的实例
给定一个矩阵matrix，由m*n个格子组成，需要从矩阵的左上角移动到右下角，且每次移动只能向右或者向下，求有多少种不同的路径
// 每个0代表一个格子
matrix = [
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0]
]
分析
dp[i][j]代表移动到当前格时的不同路径数目;
由于只能向下或向右移动，dp[i][j] = dp[i - 1] + dp[i][j - 1];
初始值和边界情况：在矩阵的最左和最上即是边界，并且初始值都只能为1;
// 时间复杂度：O(m*n)，空间复杂度O(m*n)
function solution(matrix) {
let m = matrix.length;
let n = matrix[0].length;
let dp = new Array(m);
dp[0] = new Array(n).fill(1);
for (let i = 1; i < m; i++) {
dp[i] = [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];
}
优化
本题已经传入了矩阵matrix，故可以原地修改matrix实现O(1)的空间复杂度
// 时间复杂度：O(m*n)，空间复杂度O(1)
function solution(matrix) {
let m = matrix.length;
let n = matrix[0].length;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (i == 0 || j == 0) {
matrix[i][j] = 1;
} else {
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1];
}
}
}
return matrix[m - 1][n - 1];
}
