敞开生长之旅！这是我参与「日新方案 12 月更文挑战」的第24天，点击检查活动概况。
一，动态规划概念
动态规划比较适合用来求解最优问题，比如求最大值、最小值等等。它能够十分显著地下降时刻复杂度，进步代码的履行功率。
它和递归一样都十分难学，首要学习难点在于求解问题的进程不太契合人类惯例的思维方法。
二，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))O(n*(w+1))，nn 为物品个数，ww 表明背包接受的最大分量。
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)O(2^n)、指数级，那动态规划处理方案的时刻复杂度是多少呢？来剖析一下，这个代码的时刻复杂度十分好剖析，耗时最多的部分便是代码中的两层 for 循环，所以时刻复杂度是 O(n∗w)O(n*w)。nn 表明物品个数，ww 表明背包能够承载的总分量。
虽然动态规划的时刻功率较高，可是空间复杂度为 O(n∗w)O(n*w)，对空间耗费比较大。咱们能够考虑用一个巨细为 w+1w+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，运用动态规划处理这个问题更高效。把整个求解进程分为 nn 个阶段，每个阶段会决议计划一个物品是否放到背包中。每个阶段决议计划完之后，背包中的物品的总分量以及总价值，会有多种状况，也便是会到达多种不同的状况。咱们用一个二维数组 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\cdot w)，空间复杂度也是 O(n⋅w)O(n\cdot w)。
四，总结
大部分动态规划能处理的问题，都能够通过回溯算法来处理，只不过回溯算法处理起来功率比较低，时刻复杂度是指数级的。动态规划算法，在履行功率方面，要高许多。虽然履行功率进步了，可是动态规划的空间复杂度也进步了，所以，许多时分，咱们会说，动态规划是一种空间换时刻的算法思维。
五，练习题
5.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];
}
};
参考资料
初识动态规划：怎么巧妙处理“双十一”购物时的凑单问题？
