算法动态规划

动态规划是一种将复杂问题分解为更小的子问题的优化技术

动态规划用于解决具有重复子问题的情况

动态规划 vs 分而治之

分而治之是把问题分解成相互独立的子问题，动态规划是分解成相互依赖的子问题

解题框架

首先，动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离呀等等。

既然是要求最值，核心问题是什么呢？求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗。

首先，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，需要你熟练掌握递归思维，只有列出正确的 “状态转移方程”，才能正确地穷举。而且，你需要判断算法问题是否具备 “最优子结构”，是否能够通过子问题的最值得到原问题的最值。

另外，动态规划问题存在 “重叠子问题”，如果暴力穷举的话效率会很低，所以需要你使用 “备忘录” 或者 “DP table” 来优化穷举过程，避免不必要的计算。

动态规划三要素

重叠子问题
最优子结构
状态转移方程

思维框架

明确 “状态”
明确 “选择”
定义 dp 数组/函数的含义
明确 “初始条件”

cpp

# 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
    for 选择 in 所有可能的选择:
        # 此时的状态已经因为做了选择而改变
        result = 求最值(result, dp(状态1, 状态2, ...))
    return result

cpp

# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

斐波那契数列

1、暴力递归

斐波那契数列的数学形式就是递归的，写成代码就是这样：

cpp

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

递归算法的时间复杂度怎么计算？就是用子问题个数乘以解决一个子问题需要的时间

这个算法的时间复杂度为二者相乘，即 O(1) * O(2^n) = O(2^n)，指数级别。

观察递归树，很明显发现了算法低效的原因：存在大量重复计算，比如 f(18) 被计算了两次

2、带备忘录的递归解法

明确了问题，其实就已经把问题解决了一半。即然耗时的原因是重复计算，那么我们可以造一个 “备忘录”，每次算出某个子问题的答案后别急着返回，先记到 “备忘录” 里再返回；每次遇到一个子问题先去 “备忘录” 里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。

cpp

int fib(int N) {
    // 备忘录全初始化为 0
    int[] memo = new int[N + 1];
    // 进行带备忘录的递归
    return helper(memo, N);
}

int helper(int[] memo, int n) {
    // base case
    if (n == 0 || n == 1) return n;
    // 已经计算过，不用再计算了
    if (memo[n] != 0) return memo[n];
    memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
    return memo[n];
}

本算法的时间复杂度是 O(n)，比起暴力算法，是降维打击。

3、dp 数组的递推解法

有了上一步 “备忘录” 的启发，我们可以把这个 “备忘录” 独立出来成为一张表，通常叫做 DP table，在这张表上完成 “自底向上” 的推算岂不美哉！

cpp

int fib(int N) {
    if (N == 0) return 0;
    int[] dp = new int[N + 1];
    // base case
    dp[0] = 0; dp[1] = 1;
    // 状态转移
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[N];
}

这样我们的时间复杂度是 O(n) 空间复杂度是 O(n)

这里，引出 “状态转移方程” 这个名词，实际上就是描述问题结构的数学形式

$$ f(n)=\begin {cases} 1,n=1,2 \ f(n-1)+f(n-2)，n>2 \end {cases} $$

为啥叫 “状态转移方程”？其实就是为了听起来高端，上面的几种解法中的所有操作，都是围绕这个方程式的不同表现形式。

千万不要看不起暴力解，动态规划问题最困难的就是写出这个暴力解，即状态转移方程。

4、细节优化

根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。

cpp

int fib(int n) {
    if (n == 0 || n == 1) {
        // base case
        return n;
    }
    // 分别代表 dp[i - 1] 和 dp[i - 2]
    int dp_i_1 = 1, dp_i_2 = 0;
    for (int i = 2; i <= n; i++) {
        // dp[i] = dp[i - 1] + dp[i - 2];
        int dp_i = dp_i_1 + dp_i_2;
        // 滚动更新
        dp_i_2 = dp_i_1;
        dp_i_1 = dp_i;
    }
    return dp_i_1;
}

这样我们的时间复杂度是 O(n) 空间复杂度是 O(1)

零钱兑换问题

给你 k 种面值的硬币，面值分别为 c1，c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1。

1、确定初始条件。这个很简单，显然目标金额 amount 为 0 时算法返回 0 2、确定状态。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的 “状态” 就是目标金额 amount。 3、确定选择。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的 “选择”

自顶向下递归

function coinChange(coins, amount) {
  // 题目要求的最终结果是 dp(amount)
  let cache = new Array(amount + 1).fill(-999);
  return makeChangeDP(coins, amount, cache);
}

function makeChangeDP(coins, amount, cache) {
  // 初始条件
  if (amount == 0) return 0;
  if (amount < 0) return -1;
  //  取备忘录
  if (cache[amount] != -999) return cache[amount];
  let result = Infinity;
  // 遍历coins 多个路径同时往下找
  for (let i = 0; i < coins.length; i++) {
    // 作出选择
    let coin = coins[i];
    // 状态转移方程
    let subProblem = makeChangeDP(coins, amount - coin, cache);
    // 子问题无解则跳过
    if (subProblem == -1) continue;
    result = Math.min(result, subProblem + 1);
  }
 // 存备忘录
  cache[amount] = result == Infinity ? -1 : result;
  return cache[amount];
}

console.log(coinChange([1, 2, 5, 10], 25)); // 3

dp 数组递推

function coinChange(coins, amount) {
    const dp = new Array(amount + 1).fill(amount + 1);
    // 初始条件
    dp[0] = 0;
    for (let i = 0; i < dp.length; i++) {
        for (coin of coins){
            // 子问题无解
            if (i - coin < 0) continue;
            // 状态转移
            dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
        }
    }
    // 检查是否能凑出来
    return (dp[amount] == amount + 1) ? -1 : dp[amount]
}
console.log(coinChange([1, 2, 5, 10], 25)); // 3

最后总结

第一个斐波那契数列的问题，解释了如何通过 “备忘录” 或者 “dp table” 的方法来优化递归树，并且明确了这两种方法本质上是一样的，只是自顶向下和自底向上的不同而已。

第二个凑零钱的问题，展示了如何流程化确定 “状态转移方程”，只要通过状态转移方程写出暴力递归解，剩下的也就是优化递归树，消除重叠子问题而已。

算法 动态规划 ​

动态规划 vs 分而治之 ​

解题框架 ​

斐波那契数列 ​

零钱兑换问题 ​