一文学懂动态规划

前言

在之前的一篇文章详解递归的正确打开方式中，我们详细讲解了经典的斐波那契数列问题从递归到 DP 的优化过程，

f(n)=f(n−1)+f(n−2)

class Solution {
    public int fib(int N) {
        if (N == 0) {
            return 0;
        } else if (N == 1) {
            return 1;
        }
        return fib(N-1) + fib(N-2);
    }
}

体会了递归的思想，

即：

递归的实质是能够把一个大问题分解成比它小点的问题，然后我们拿到了小问题的解，就可以用小问题的解去构造大问题的解。

但缺点就是随着 n 值的增大，递归树 Recursion Tree 变的越来越深，相应需要计算的节点也越来越多。

且好多节点值进行了重复的计算，通过分析我们知道其时间复杂度为：

O(2^n)O(2n)

指数级别的时间复杂度对超算来说都是噩梦...

上一篇讲递归的文章我们也给出了相应优化的方案，即用一个数组，最后只用两个变量来保存计算过的节点结果。

class Solution {
    public int fib(int N) {
        int a = 0;
        int b = 1;
        if(N == 0) {
            return a;
        }
        if(N == 1) {
            return b;
        }
        for(int i = 2; i <= N; i++) {
            int tmp = a + b;
            a = b;
            b = tmp;
        }
        return b;
    }
}

这样我们瞬间将时间复杂度降到了 O(n)，空间复杂度也变成了 O(1)。(具体时空复杂度分析请戳这里)

思路分析

那么回顾一下我们怎么做的呢？

我们将自顶向下的递归，变成了自底向上的 for loop。

我们将每次计算出来的节点值予以保存，这样就不再需要重复计算一些已经计算过的节点，这也称为剪枝 pruning。

这样我们便引出了动态规划的核心思想：

动态规划（英语：Dynamic programming，简称 DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。

大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其[记忆化存储，以便下次需要同一个子问题解之直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

好多人说动态规划是处理复杂问题优化算法的二向箔，而我想说，

说的没毛病...

小插曲：

大家应该都听过 NP=?P 问题，这是美国克雷数学研究院百万美金悬赏的七个千僖数学难题之首（关于 NP 问题我之后还会详细的写文章描述）。

那这跟我们今天说的动态规划有什么关系呢？

动态规划有一类典型的问题叫背包问题的题目，而背包问题就是典型的NPC问题（非确定性多项式完备问题 _Non-deterministic Polynomial_），这个大家先做个了解，只是一个引子，我们提到这些，无非是要说明动态规划作为能处理 NPC 问题的最优化算法还是属实有点东西的。（当然这跟数学证明 NP=?P 是两码事，毕竟头号千禧难题还没有被攻破...）所以大家一定先要学好动态规划呀～

动态规划核心

回到上文描述的动态规划定义，我们根据定义提炼出动态规划最主要的核心，即：

1. 重叠子问题

2. 最优子结构

这里我再加个

1. 状态转移方程

1. 重叠子问题

根据斐波那契数列的例子，我们知道，当前的数只与它前面两个数有关，即文章开头的

f(n) = f(n-1)+f(n-2)f(n)=f(n−1)+f(n−2)

我们要想求出 f(n)，就得求出 f(n-1)和 f(n-2)

这个就是属于重叠子问题，即：

将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。

这里捎带强调一个概念：

无后效性：要求出 f(n)，只需求出 f(n-1)和 f(n-2)的值，而 f(n-1)和 f(n-2)是如何算出来的，对之后的问题没有影响，即“未来与过去无关”，这就是无后效性。

上述的重叠子问题的子问题也必须满足无后效性这个概念。

2. 最优子结构

那么什么是最优子结构呢？

最优即最值，斐波那契数列例子里并没有提及和最值相关的字眼，故该例子严格来说并不能算完全的动态规划问题。

下面我们介绍另一个经典例题 ：

零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

这个题乍一看大概思路好像是：那我们就每次先找出最大面额的硬币试试呀，然后在总面额里减去，再依次取到较小的面额，直到凑够 amount（贪心思路）。

这个想法好像看似完全可行，但如果给你以下这组数据呢？

示例 3:

输入：coins = [1, 5, 11], amount = 15输出：3解释：15 = 5 + 5 + 5

但是如果我们沿用上述贪心算法

输出：5

解释：11 + 1 + 1 + 1 + 1

而后一种得出的结果显而错误，所以我们发现贪心算法对此题不同的数据竟不是一通百通，所以说明我们这种策略不对。

那策略哪里出问题了呢？

贪心只顾眼前，先找最大面额 11，而忽略了后续找 4 个 1 块硬币的代价，1 + 4 总共需要 5 枚，贪心算法在这种问题面前就有点鼠目寸光了...

而这个题就是典型的动态规划问题，下面我们进一步分析：

上文提到，动态规划最核心的条件和性质就只有三个，我们依次按这三点开始分析。

1. 重叠子问题

思考：要凑出 15 块钱，我们能不能先凑出 15 块钱之前（比当前问题更小的问题）的事情？

那么小问题是什么呢？

我们发现，面额分别为 1，5，11。

1. 我们可以先凑出 11 块（此时我们已经用了一枚 11 块的硬币，硬币数+1），然后再凑出 15 - 11 = 4 块。

假设 f(n)表示凑出 n 元所需要的最少硬币数， 那么这样我们凑出 15 块所需要的硬币总数为 f(15) = f(4) + 1。

2. 我们也可以先凑出 5 块，然后再凑出 15 - 5 = 10 块。

即 f(15) = f(10) + 1

3. 我们也可以先凑出 1 块，然后再凑出 15 - 1 = 14 块。

即 f(15) = f(14) + 1

我们发现想要凑出一个较大数目的金额，可以先凑出较小数目的金额。

这不就是重叠子问题吗？

将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。

我们进一步发现，这些子问题同样满足无后效性，即我先凑出 11 块，还剩 4 块要凑，我即将凑出 4 块的策略与你已经凑出 11 块的策略并不存在半毛钱的关系。。

即上文所说的：“未来与过去无关”，这就是无后效性。

2.最优子结构

由上我们发现：

f(n) 只与 f(n-1)，f(n-5)，f(n-11) 的值相关。

然后题目是求：问凑出金额所需最少的硬币数量。

我们的 f(n) 也是这么定义的：f(n) 表示凑出 n 元所需要的最少硬币数。

即根据 f(n - 1)，f(n - 5)，f(n - 11) 的最优解，我们即可得到 f(15) 的最优解。

大问题的最优解可以由小问题的最优解得到，这不就是最优子结构性质吗？

根据以上我们就可以顺理成章的写出动态规划问题里最难写出的状态转移方程了

3.状态转移方程

f(n) = min[f(n -1),f(n -5),f(n - 11)] + 1f(n)=min[f(n−1),f(n−5),f(n−11)]+1

听上去高大上，实则，就这？？？

没错，就这。

细心的读者会发现：这不就跟 斐波那切数列 的递推公式

f(n) = f(n-1)+f(n-2)f(n)=f(n−1)+f(n−2)

类似吗？

对，它们俩大体上就是一个东西，即：递归方程。

递归代表着重复，重复，再重复...

说白了计算机天生就是干重复事情的，这也是属于计算机唯一的美，暴力美，之所以计算机看似那么“聪明”，实则是人类智慧的结晶在告诉计算机：你应该美的暴力，优雅的暴力，而不是直接暴力的暴力，这就是算法的力量。

所以，当我们按部就班的分析出动态规划问题的前两个性质，写出状态转移方程其实也不怎么难，所以也不要被任何高大上的术语吓到，盘它就完事儿了。

然后回忆我们前文的内容，斐波那切数列的例子，我们如何将暴力的递归改造成优雅的动态规划的呢？

• 将自顶向下的递归，变成了自底向上的 for loop。

• 将每次计算出来的节点值予以保存。

将斐波那切数列稍加改造，我们即可写出此题的代码。

Fibonacci 例子中，我们用 notes[n] 来表示输入 n 时的返回值答案，这里我们统一用 dp table.

即用 dp[amount] 表示：当输入金额为 amount 时，可兑换的最少硬币数。

所以我们首先先创建一个 dp table 用来存储对应解，即：

int[] dp = new int[amount+1];

为什么大小是amount + 1不是amount呢？

答：因为我们 dp[amount] 的含义是当金额为amount时，凑出amount的最少硬币数量。

假设amount = 10，如果我们 new 一个 size 为 10 的数组，那么我们取 dp[amount] 时就越界了，故当我们要取到 dp[amount] 时，数组大小得为 int[amount + 1]。

然后将

dp[0] = 0;

解释：当金额为0元时，找出0个硬币。

紧接着最主要的问题来了，也是最难写的一部分代码，前文提到说，将递归改为动态规划最显著的一个特点是：

我们将自顶向下的递归，变成了自底向上的 for loop。

自顶向下很好写，因为直接递归嘛：

// Fibonacci
public int fib(int N) {
        if (N == 0) {
            return 0;
        } else if (N == 1) {
            return 1;
        }
        return fib(N-1) + fib(N-2);
    }

我们只需要在 base case 处判断，并返回相应的值，然后直接进行递归函数调用。

那么我们如何转变成动态规划，自底向上呢?

这个时候就需要 for 循环（简单但又强大的 for loop）。

上文里我们已经得出了状态转移方程：

f(n) = min[f(n -1),f(n -5),f(n - 11)] + 1f(n)=min[f(n−1),f(n−5),f(n−11)]+1

假设一组数据是这样：

coins = {1,2,5,7,10} amount = 14

首先我们建立 dp table:

int[] dp = int[15];

初始化 dp[0] = 0

我们考虑这样自底向上 写：

用变量 i 从 1 循环至 amount，依次计算金额 1 至 amount 的最优解，即 dp[amount]。

我们可以写出第一层 for 循环：

for(int i = 1;i <= amount;i++){
            ...
}

然后：对于每个金额 i，使用变量 j 遍历硬币面值 coins[] 数组：

对于所有小于等于 i 的面值 coins[j]，找出最小的 i - coins[j] 金额的最优解 dp[i - coins[j]]。

那么 dp[i] 的最优解即为 dp[i - coins[j]] + 1。

如下图所示：

假如当前 i 指向金额 6，

对于所有小于等于 6 的面额 coins[j]，即coins[0]，coins[1]，coins[2] 分别为 1，2，5。

找出最小的 6 - coins[j] 金额的最优解 dp[i - coins[j]]，即：

6 - 1 = 5 dp[5] = 1

6 - 2 = 4 dp[4] = 2

6 - 5 = 1 dp[1] = 1

那么 dp[i]的最优解即为 dp[i - coins[j]] + 1

dp[6] = min(dp[1],dp[4],dp[5]) + 1

由以上可知：dp[6] = 1 + 1 = 2

后续依次计算...

由此，我们可以写出里层的 for 循环：

//来一个整型最大数，保证其它数第一次和这个数比较时都比这个数小
//变量名叫min，这是对应外层i循环，即:求每个dp[i]的最优解
int min = Integer.MAX_VALUE;
for(int j = 0;j < coins.length;j++){
    //所有小于等于i的面值coins[j]，并且最优解小于默认最大值
    if(coins[j] <= i && dp[i - coins[j]] < min){
            min = dp[i - coins[j]] + 1;//更新dp
    }
}
    dp[i] = min;

这个 for 循环，这也是此题思想代码的核心。

我们将两个 for 循环写一起，即写出了完整代码：

class Solution {
  public int coinChange(int[] coins, int amount) {
      if(coins.length == 0) return -1;
      int[] dp = new int[amount + 1];
      dp[0] = 0;
      for(int i = 1;i <= amount;i++){
        int min = Integer.MAX_VALUE;
        for(int j = 0;j < coins.length;j++){
          if(coins[j] <= i && dp[i - coins[j]] < min){
            min = dp[i - coins[j]] + 1;
          }
        }
        dp[i] = min;
      }
      return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
  }
}

这就是自底向上的写法，也是动态规划的核心。

总结

我们再回顾整个流程，如何尝试去处理一个动态规划问题？

1. 首先分析这个问题符不符合动态规划最重要的前两个性质（重叠子问题，最优子结构）；

2. 如果满足前两个性质，那么我们尝试写出状态转移方程，也即递归式；

3. 优化：将自顶向下的递归式（_函数调用_）改为自底向上的动态规划（_for loop_）

好了，今天的动态规划问题到此就结束啦，当然动态规划的威力还远不止于此，关于动态规划更多的内容，我们后续再见～