总结一下动态规划的思路

逃离我推掉我的手 2023-07-25 12:38 11阅读 0赞

## 写在前面 ##

我相信只要是接触算法的同学，就一定会接触DP，也就是动态规划，虽然经常遇见动态规划相关的算法题，但是许多人还是有些畏惧，不过我相信只要你愿意静下来学习总结，看看这篇文章或者其他优秀的讲解文章，不管你之前是否害怕动态规划系列的问题，相信足以帮助你消除对动态规划算法的恐惧，因为动态规划其实就是套路中，寻求变数。只要有掌握了套路，就能灵活应对。

## 聊一聊动态规划的思想 ##

动态规划问题的⼀般形式就是求最值。动态规划其实是运筹学的⼀种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离呀等等。换句话说，动态规划是：通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。它的主要思想就是：若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

而我们把这种记忆化存储叫做`「备忘录」`或者`「DP table」`来优化穷举过程。而且，动态规划问题一定会具备`「最优子结构」`，才能通过子问题的解得到原问题的解。另外，由于我们解决子问题时，依托先前另外已经求出的子问题的解，所以，我们需要寻找到子问题之间的依赖关系，也就是列出正确的`「状态转移方程」`。

以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素，其中，写出状态转移方程是最困难的。我们可以通过如下方式思考：

明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case

下面通过斐波那契数列问题和凑零钱问题来详解动态规划的基本原理。前者主要是让你明白什么是重叠子问题（斐波那契数列严格来说不是动态规划问题），后者主要集中于如何列出状态转移方程。

## 斐波那契数列问题 ##

### 暴力递归 ###

斐波那契数列数列我就不多讲了吧，不过还是为了部分同学可能忘记了，我这里就简单的多提一下，斐波那契数列：除第一个和第二个数都等于`1`之外，其余的数，都等于该数的前两个数之和。怎么样，解释的够简单吧，如果还是没有唤起你的记忆，你就自行百度吧，这里点到为止。斐波那契数列的数学形式就是递归的，写成代码就是这样：

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

这个不用多说了，学校老师讲递归的时候似乎都是拿这个举例。我们也知道这样写代码虽然简洁易懂，但是十分低效，低效在哪里？假设 n = 6的时候，画出递归树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center]  
这个递归树怎么理解？就是说想要计算原问题`f(6)`，我就得先计算出子问题`f(5)`和`f(4)`，然后要计算`f(5)`，我就要先算出子问题`f(4)`和`f(3)`，以此类推。最后遇到`f(1)`或者`f(2)`的时候，结果已知，就能直接返回结果，递归树不再向下生长了。递归算法的时间复杂度怎么计算？子问题个数乘以解决一个子问题需要的时间。子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 O ( 2 n ) O(2^n) O(2n)。解决一个子问题的时间，在本算法中，没有循环，只有 f ( n − 1 ) + f ( n − 2 ) f(n-1)+f(n-2) f(n−1)\+f(n−2)一个加法操作，时间为  O ( 1 ) O(1) O(1)。所以，这个算法的时间复杂度为  O ( 2 n ) O(2^n) O(2n)，指数级别，爆炸。

观察递归树，很明显发现了算法低效的原因：存在大量重复计算，比如`f(4)`被计算了两次，而且你可以看到，以`f(4)`为根的这个递归树体量巨大，多算一遍，会耗费巨大的时间。更何况，还不止`f(4)`这一个节点被重复计算，所以这个算法及其低效。这就是动态规划问题的第一个性质：重叠子问题。下面，我们想办法解决这个问题。

### 带备忘录的递归解法 ###

明确了问题，其实就已经把问题解决了一半。即然耗时的原因是重复计算，那么我们可以造一个`「备忘录」`，每次算出某个子问题的答案后别急着返回，先记到`「备忘录」`里再返回；每次遇到一个子问题先去`「备忘录」`里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。一般使用一个数组充当这个`「备忘录」`，当然你也可以使用`哈希表（字典）`，思想都是一样的。

public int fib(int N) { 
        if (N < 1) return 0;
        // 备忘录全初始化为 0，Java中直接创建int数组，就默认0
        int[] memo = new int[N + 1];
        // 初始化最简情况
        return helper(memo, N);
    }
    
    public int helper(int[] memo, int n) { 
        // base case 
        if (n == 1 || n == 2) return 1;
        // 已经计算过
        if (memo[n] != 0) return memo[n];
        memo[n] = helper(memo, n - 1) + 
                    helper(memo, n - 2);
        return memo[n];
    }

现在，画出递归树，你就知道「备忘录」到底做了什么：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 1]  
实际上，带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 2]  
递归算法的时间复杂度怎么算？子问题个数乘以解决一个子问题需要的时间。子问题个数，即图中节点的总数，由于本算法不存在冗余计算，子问题就是`f(1),f(2),f(3)…f(20)`，数量和输入规模  n = 20 n = 20 n=20 成正比，所以子问题个数为 O ( n ) O(n) O(n)。解决一个子问题的时间，同上，没有什么循环，时间为  O ( 1 ) O(1) O(1)。所以，本算法的时间复杂度是  O ( n ) O(n) O(n)。比起暴力算法，是降维打击。至此，带备忘录的递归解法的效率已经和迭代的动态规划一样了。实际上，这种解法和迭代的动态规划思想已经差不多，只不过这种方法叫做`「自顶向下」`，动态规划叫做`「自底向上」`。

啥叫`「自顶向下」`？注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从一个规模较大的原问题比如说`f(20)`，向下逐渐分解规模，直到`f(1)`和`f(2)`触底，然后逐层返回答案，这就叫`「自顶向下」`。啥叫`「自底向上」`？反过来，我们直接从最底下，最简单，问题规模最小的`f(1)`和`f(2)`开始往上推，直到推到我们想要的答案`f(20)`，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。

### dp 数组的迭代解法 ###

有了上一步「备忘录」的启发，我们可以把这个「备忘录」独立出来成为一张表，就叫做 DP table 吧。

public int fib(int N) { 
        int[] dp = new int[N + 1];
        // base case
        dp[1] = dp[2] = 1;
        for (int i = 3; i <= N; i++)
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[N];
    }

怎么样，你发现这个 DP table 特别像之前那个「剪枝」后的结果，只是反过来算而已。实际上，带备忘录的递归解法中的「备忘录」，最终完成后就是这个 DP table，所以说这两种解法其实是差不多的，大部分情况下，效率也基本相同。这里，引出「状态转移方程」这个名词，实际上就是描述问题结构的数学形式：  
![在这里插入图片描述][20200415154506311.png_pic_center]  
为啥叫「状态转移方程」？为了听起来高端。你把 f(n) 想做一个状态 n，这个状态 n 是由状态 n - 1 和状态 n - 2 相加转移而来，这就叫状态转移，仅此而已。你会发现，上面的几种解法中的所有操作，例如 `return f(n - 1) + f(n - 2)，dp[i] = dp[i - 1] + dp[i - 2]`，以及对备忘录或 DP table 的初始化操作，都是围绕这个方程式的不同表现形式。可见列出「状态转移方程」的重要性，它是解决问题的核心。很容易发现，其实状态转移方程直接代表着暴力解法。

千万不要看不起暴力解，动态规划问题最困难的就是写出状态转移方程，即这个暴力解。优化方法无非是用备忘录或者 DP table，再无奥妙可言。这个例子的最后，讲一个细节优化。细心的读者会发现，根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)：

public int fib(int n) { 
        if (n == 2 || n == 1) 
            return 1;
        int prev = 1, curr = 1;
        for (int i = 3; i <= n; i++) { 
            int sum = prev + curr;
            prev = curr;
            curr = sum;
        }
        return curr;
    }

## 凑零钱问题 ##

先看下题目：给你 k k k种面值的硬币，面值分别为 c 1 , c 2... c k c1, c2 ... ck c1,c2...ck，每种硬币的数量无限，再给一个总金额 a m o u n t amount amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回  − 1 -1 −1 。算法的函数签名如下：

// coins 中是可选硬币面值，amount 是目标金额
    int coinChange(int[] coins, int amount);

比如说 k = 3 k = 3 k=3，面值分别为  1 ， 2 ， 5 1，2，5 1，2，5，总金额 a m o u n t = 11 amount = 11 amount=11。那么最少需要  3 3 3枚硬币凑出，即  11 = 5 + 5 + 1 11 = 5 + 5 + 1 11=5\+5\+1。你认为计算机应该如何解决这个问题？显然，就是把所有肯能的凑硬币方法都穷举出来，然后找找看最少需要多少枚硬币。

### 暴力递归 ###

首先，这个问题是动态规划问题，因为它具有「最优子结构」。要符合「最优子结构」，子问题间必须互相独立。啥叫相互独立？你肯定不想看数学证明，我用一个直观的例子来讲解。比如说，你的原问题是考出最高的总成绩，那么你的子问题就是要把语文考到最高，数学考到最高…… 为了每门课考到最高，你要把每门课相应的选择题分数拿到最高，填空题分数拿到最高…… 当然，最终就是你每门课都是满分，这就是最高的总成绩。得到了正确的结果：最高的总成绩就是总分。因为这个过程符合最优子结构，“每门科目考到最高”这些子问题是互相独立，互不干扰的。

但是，如果加一个条件：你的语文成绩和数学成绩会互相制约，此消彼长。这样的话，显然你能考到的最高总成绩就达不到总分了，按刚才那个思路就会得到错误的结果。因为子问题并不独立，语文数学成绩无法同时最优，所以最优子结构被破坏。回到凑零钱问题，为什么说它符合最优子结构呢？比如你想求 a m o u n t = 11 amount = 11 amount=11时的最少硬币数（原问题），如果你知道凑出 a m o u n t = 10 amount = 10 amount=10的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为  1 1 1 的硬币）就是原问题的答案，因为硬币的数量是没有限制的，子问题之间没有相互制，是互相独立的。

那么，既然知道了这是个动态规划问题，就要思考如何列出正确的状态转移方程。先确定「状态」，也就是原问题和子问题中变化的变量。由于硬币数量无限，所以唯一的状态就是目标金额 a m o u n t amount amount。然后确定 d p dp dp函数的定义：函数  d p ( n ) dp(n) dp(n)表示，当前的目标金额是 n n n，至少需要 d p ( n ) dp(n) dp(n)个硬币凑出该金额。然后确定「选择」并择优，也就是对于每个状态，可以做出什么选择改变当前状态。具体到这个问题，无论当的目标金额是多少，选择就是从面额列表coins中选择一个硬币，然后目标金额就会减少：

# 伪码框架
    public int coinChange(List<Integer> coins, int amount){ 
    	# 做选择，需要硬币最少的那个结果就是答案
    	if(amount == 0) return 0;
    	if(amount < 0) return -1;
    	int res = Integer.MAX_VALUE;
        for (coin : coins)
            res = min(res, 1 + coinChange(coins, amount - coin));
    	
    	return res;
    }

最后明确 base case，显然目标金额为  0 0 0 时，所需硬币数量为  0 0 0；当目标金额小于  0 0 0 时，无解，返回 − 1 -1 −1：

public int coinChange(List<Integer> coins, int amount){ 
    	if (amount == 0) return 0;
        if (amount < 0) return -1;
        # 求最小值，所以初始化为正无穷
        int res = Integer.MAX_VALUE;
        for (coin : coins){ 
            subproblem = dp(coins, n - coin);
            # 子问题无解，跳过
            if (subproblem == -1) continue;
            res = min(res, 1 + subproblem);
    	}
    	if(res != Integer.MAX_VALUE) return res;
    	else return -1;
    }

至此，状态转移方程其实已经完成了，以上算法已经是暴力解法了，以上代码的数学形式就是状态转移方程：  
![在这里插入图片描述][2020041516185875.png_pic_center]  
至此，这个问题其实就解决了，只不过需要消除一下重叠子问题，比如 a m o u n t = 11 , c o i n s = 1 , 2 , 5 amount = 11, coins = \{1,2,5\} amount=11,coins=1,2,5时画出递归树看看：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 3]

### 带备忘录的递归 ###

只需要稍加修改，就可以通过备忘录消除子问题：

# 备忘录
    memo = dict()
    public int coinChange(List<Integer> coins, int amount){ 
    	# 查备忘录，避免重复计算
    	if (n in memo)  return memo[n];
    	if (amount == 0) return 0;
        if (amount < 0) return -1;
        # 求最小值，所以初始化为正无穷
        int res = Integer.MAX_VALUE;
        for (coin : coins){ 
            subproblem = dp(coins, n - coin);
            # 子问题无解，跳过
            if (subproblem == -1) continue;
            res = min(res, 1 + subproblem);
    	}
    	if(res != Integer.MAX_VALUE) return memo[n] = res;
    	else return memo[n];
    }

### dp 数组的迭代解法 ###

当然，我们也可以自底向上使用 dp table 来消除重叠子问题，dp数组的定义和刚才dp函数类似，定义也是一样的：`dp[i] = x`表示，当目标金额为`i`时，至少需要`x`枚硬币。

public int coinChange(int[] coins, int amount) { 
        // 数组大小为 amount + 1，初始值也为 amount + 1
        int[] dp = new int[amount + 1];
        for(int i = 0; i < amount + 1; i++}
        	dp[i] = amount + 1;
        // base case
        dp[0] = 0;
        for (int i = 0; i < dp.size(); i++) { 
            // 内层 for 在求所有子问题 + 1 的最小值
            for (int coin : coins) { 
                // 子问题无解，跳过
                if (i - coin < 0) continue;
                dp[i] = min(dp[i], 1 + dp[i - coin]);
            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 4]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/28e358b65f284d368784e4691e6af320.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230528/9786dbede89e4bb384ac616a75a99aaa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230528/8fdab8ea227749dba7377ef9874e5cba.png
[20200415154506311.png_pic_center]: /images/20230528/bc63b82c2a3143b49e3aa854b8c0e61f.png
[2020041516185875.png_pic_center]: /images/20230528/5699968299d5497f93fcdb31cb69f04e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20230528/9849c89bd20148449384a6642980ce1e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20230528/fb31e914192949dd9ea3517e725dafb4.png