本文分享自华为云社区《深入浅出动态规划算法(上)-云社区-华为云》，作者：嵌入式视觉。

一、动态规划概念

动态规划比较适合用来求解最优问题，比如求最大值、最小值等等。它可以非常显著地降低时间复杂度，提高代码的执行效率。

它和递归一样都非常难学，主要学习难点在于求解问题的过程不太符合人类常规的思维方式。

二、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 个物品    }};

把整个求解过程分为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];    }};

初识动态规划：如何巧妙解决“双十一”购物时的凑单问题？

关注#华为云开发者联盟# 点击下方，第一时间了解华为云新鲜技术~

华为云博客_大数据博客_AI博客_云计算博客_开发者中心-华为云