本文分享自华为云社区《深入浅出动态规划算法》，作者：嵌入式视觉。
一、动态规划概念
动态规划比较适合用来求解最优问题，比如求最大值、最小值等等。它可以非常显著地降低时间复杂度，提高代码的执行效率。
它和递归一样都非常难学，主要学习难点在于求解问题的过程不太符合人类常规的思维方式。
二、0-1 背包问题
对于一组不同重量、不可分割的物品，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，背包中物品总重量的最大值是多少呢？
关于这个 0-1 背包问题，上一节学习了回溯的解决方法，也就是穷举搜索所有可能的装法（时间复杂度指数级），然后找出满足条件的最大值。有没有什么规律，可以有效降低时间复杂度呢？
1、回溯法的求解过程：
直接看代码，规律是不好的，画个求解过程图（递归树）会好看些。假设背包的最大承载重量是 9，有 5 个不同的物品，每个物品的重量分别是 2，2，4，6，3。求解过程的递归树如下图所示。
递归树中的每个节点表示一种状态，我们用（i, cw）来表示。其中，i 表示将要决策第几个物品是否装入背包，cw 表示当前背包中物品的总重量。比如，（2，2） 表示我们将要决策第 2 个物品是否装入背包，在决策前，背包中物品的总重量是 2。这里使用回溯算法，从递归树中可以发现其中有些子问题的求解是重复的，且时间复杂度是指数级的。
使用”备忘录”（记忆化递归）的解决方式，记录已经计算好的 f(i, cw)，当再次计算到重复的 f(i, cw) 的时候，可以直接从备忘录中取出来用，就不用再递归计算了，这样就可以避免冗余计算。
int maxW = 0;int weight[6] = {2,2,4,6,3}; // 物品重量int n = 5; // 物品个数 int w = 9; // 背包承受的最大重量bool mem[5][10]; // 备忘录，默认值false
// 记忆化递归算法实现class SolutionBacktracking{public: void f(int i, int cw){ // i 表示放第 i 个物品，cw 表示当前装进背包的物品的重量和 if (cw == w || i == n) { // cw==w表示装满了，i==n表示物品都考察完了 if(cw > maxW) maxW = cw; return; } if(mem[i][cw]) return; // 重复状态 mem[i][cw] = true; // 记录状态
f(i+1, cw); // 不放第 i 个物品 if(cw+weight[i] <= w) f(i+1, cw+weight[i]); // 放第 i 个物品 }};
复制代码
这里依然是基于回溯算法实现的，但是采用了记忆化递归的方法，时间复杂度和空间复杂度都是 O(n∗(w+1))，n 为物品个数，w 表示背包承受的最大重量。
2、动态规划求解过程如下：
把整个求解过程分为 n 个阶段，每个阶段会决策一个物品是否放到背包中。每个物品决策（放入或者不放入背包）完之后，背包中的物品的重量会有多种情况，也就是说，会达到多种不同的状态，对应到递归树中，就是有很多不同的节点。
我们把每一层重复的状态（节点）合并，只记录不同的状态，然后基于上一层的状态集合，来推导下一层的状态集合。我们可以通过合并每一层重复的状态，这样就保证每一层不同状态的个数都不会超过 w 个（w 表示背包的承载重量），也就是例子中的 9。于是，我们就成功避免了每层状态个数的指数级增长。动态规划方法的计算过程如下图：
我们用一个二维数组 states[n][w+1]，来记录每层可以达到的不同状态。0-1 背包问题的动态规划解法的 C++ 代码如下：
class SolutionDP1{public: // weight:物品重量，n:物品个数，w:背包可承载重量 int knapsack1(int weight[], int n, int w){ vector<vector<bool> >states(n, vector<bool>(w+1, false)); // 初始化 states 第一个阶段的状态 states[0][0] = true; // 第一个物品不放进背包 if(weight[0] <= w) states[0][weight[0]] = true; // 第一个物品放进背包 // 动态规划-分阶段 for(int i=1; i<n;i++){ for(int j=0; j<w; j++) { // 第 i 个物品不放进背包{} if(states[i-1][j]) states[i][j] = states[i-1][j]; } for(int j=0; j<=w-weight[i];j++){ // 第 i 个物品放入背包 if(states[i-1][j]) states[i][j+weight[i]] = true; } }
// 在最后一层变量找到最接近 w 的重量并输出结果 for(int i=w; i>0; i--){ if(states[n-1][i]) return i; } return 0; }};
复制代码
这就是一种用动态规划解决问题的思路。我们把问题分解为多个阶段，每个阶段对应一个决策。我们记录每一个阶段可达的状态集合（去掉重复的），然后通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态地往前推进。这也是动态规划这个名字的由来，你可以自己体会一下
首先，可以分解为多阶段，其次，状态去重，最后当前阶段可以利用上一个阶段来获取。这是动态规划的关键。
我们知道回溯算法解决这个问题的时间复杂度是 O(2n)、指数级，那动态规划解决方案的时间复杂度是多少呢？来分析一下，这个代码的时间复杂度非常好分析，耗时最多的部分就是代码中的两层 for 循环，所以时间复杂度是 O(n∗w)。
n 表示物品个数，w 表示背包可以承载的总重量。
虽然动态规划的时间效率较高，但是空间复杂度为 O(n∗w)，对空间消耗比较大。我们可以考虑用一个大小为 w+1 的一维数组代替二维数组，减少内存消耗。代码如下：
class SolutionDP2{public: // weight:物品重量，n:物品个数，w:背包可承载重量 int knapsack2(int weight[], int n, int w){ vector<bool> states(w+1, false); // int *states=new int [m+1]; // 动态分配,数组长度为 m states[0] = true; // 第一个物品不放进背包 if(weight[0] < w) states[weight[0]] = true; // 第一个物品放进背包 // 动态规划-分阶段 for(int i=1; i<n;i++){ for(int j=w-weight[i]; j>=0; j--) { // 第 i 个物品放进背包 if(states[j]) states[j+weight[i]] = true; } }
// 在最后一层变量找到最接近 w 的重量并输出结果 for(int i=w;i>0;i--){ if(states[i]) return i; } return 0; }};
复制代码
程序分析：遍历每个物品，将该物品放入背包时，在不超过最大重量的前提下，再遍历查看之前的放入记录，将之前可能出现的重量的和当前物品的重量相加再记录下来，等所有方案都尝试过后，可能出现的背包重量也都被记录下来了，最后，从中选择一个最大值返回。
三、0-1 背包问题升级版
前面讲的背包问题，只涉及背包重量和物品重量。现在引入物品价值这一变量。对于一组不同重量、不同价值、不可分割的物品，我们选择将某些物品装入背包，在满足背包最大重量限制的前提下，背包中可装入物品的总价值最大是多少呢？
1、这个问题依旧可以先用回溯算法来解决，代码如下：
// 0-1 背包问题升级版的回溯解法int maxV = 0; // 结果放到maxV中int weight[] = {2，2，4，6，3}; // 物品的重量int value[] = {3，4，8，9，6}; // 物品的价值int n = 5; // 物品个数int w = 9; // 背包承受的最大重量
class Solution{public: void f(int i, int cw, int cv) { // 调用f(0, 0, 0) if (cw == w || i == n) { // cw==w表示装满了，i==n表示物品都考察完了 if(cv > maxV) maxV = cv; return; } if(cv > maxV) maxV = cv; f(i+1, cw, cv); // 不放第 i 个物品 if(cw+weight[i] <= w) f(i+1, cw+weight[i], cv+value[i]) // 放第 i 个物品 }};
复制代码
2、使用动态规划解决这个问题更高效。
把整个求解过程分为 n 个阶段，每个阶段会决策一个物品是否放到背包中。每个阶段决策完之后，背包中的物品的总重量以及总价值，会有多种情况，也就是会达到多种不同的状态。我们用一个二维数组 states[n][w+1]，来记录每层可以达到的不同状态。
class SolutionDP3{ int knapsack3(int weight[], int value[], int n, int w) { vector<vector<int> > states(n, vector<int>(w+1, -1)); states[0][0] = 0; // 不放入第 0 个物品 if(weight[0] < w) states[0][weight[0]] = value[0]; // 放入第 0 个物品
for(int i=1; i<n; i++){ for(int j=0; j< w; j++){ // 不放入第 i 个物品 if(states[i-1][j]) states[i][j] = states[i-1][j]; }
for(int j=0; j< w-weight[i]; j++){ // 放入第 i 个物品 int v = states[i-1][j] + values; if(v > states[i][j+weight[i]]) states[i][j+weight[i]] = v; } }
int maxV = -1; for(int j = w; j>=0; j--){ if(states[n-1][j] > maxV) maxV = states[n-1][j]; }
return maxV; }}
复制代码
代码的时间复杂度是 O(n⋅w)，空间复杂度也是 O(n⋅w)。
四、总结
大部分动态规划能解决的问题，都可以通过回溯算法来解决，只不过回溯算法解决起来效率比较低，时间复杂度是指数级的。动态规划算法，在执行效率方面，要高很多。尽管执行效率提高了，但是动态规划的空间复杂度也提高了，所以，很多时候，我们会说，动态规划是一种空间换时间的算法思想。
五、练习题
1、leetcode322 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
动态规划解法的 C++ 代码如下：
class Solution {public: int coinChange(vector<int>& coins, int amount) { int Max = amount + 1; vector<int> dp(amount + 1, Max); dp[0] = 0; for (int i = 1; i <= amount; ++i) { for (int j = 0; j < (int)coins.size(); ++j) { if (coins[j] <= i) { dp[i] = min(dp[i], dp[i - coins[j]] + 1); } } } return dp[amount] > amount ? -1 : dp[amount]; }};
复制代码
参考资料
初识动态规划：如何巧妙解决“双十一”购物时的凑单问题？
点击关注，第一时间了解华为云新鲜技术~
评论