动态规划详细讲解c++|经典例题讲解认识动态规划|0-1背包问题详解

引言

uu们，你们好！这次的分享是动态规划，其中介绍了动态规划的相关概念和做题模板（三要素），同时为了uu们对动态规划方法有更加形象的认识，特地找了两个经典问题，和大家一起分析。并且呢，为了大家检验自己的学习成果，我专门在常用的oj上为uu们找到了相关题目的链接，大家可以自行编写代码、提交检验。我在首页创建了一个动态规划的专栏，本文章是第一篇。之后，会在该专栏更新自己的刷题日记，每次都会给出oj题目链接和AC过的思路、代码分享。如果有想一起学习的小伙伴，可以点赞&收藏&关注，为咱们互联网上的这份缘分加把锁，以防轻易走丢。谢谢大家咯嘻嘻！！
不过，让我没想到的是这篇文章足足写了小两天，之前学动态规划和用动态规划的时候，一直以为自己还算掌握了，可真要自己一字一句讲清楚逻辑，还是费了不少功夫的，当然在这个过程中也有新的收获，温故而知新如是也。所以呢，在此也推荐uu们平常也可以坚持分享博客，记录自己的成长历程，而且这也能不断push我们个人前进！

基本概念

动态规划（Dynamic Programming，常称dp）又称为记录结果再利用的方法，求问题的最优解

贝尔曼等人提出最优化原理：

一个最优化策略的子策略总是最优的；
一个问题满足最优化原理称其具有最优子结构性质

一个问题如果满足最优子结构性质和子问题重叠性质，那么就可以使用动态规划法解决。

对于最优化原理的简单理解：假如有问题 a，a 由两个子问题 b，c 组成；对于问题 a 有解（即上边的最优化策略） x，x 可以分解成 y 和 z 两部分；如果y、z 分别是 b、c 的解（最优化策略），那么就成该问题具有最优子结构性质。
子问题重叠性质即在不同父问题的解中包含相同子问题的解。

因为拥有最优子结构性质，所以可以由子问题的解得到原问题的解；因为子问题重叠性质，所以记录结果就有了意义，我们可以在第一次求解问题后记录下解的值，这样在之后用到该问题的解时，直接访问就行不需要再次求解了。

求解阶乘

接下来，我们将通过分析阶乘问题的求解，来进一步理解最优子结构和子问题重叠的性质。

当我们使用递归来求阶乘时：

int f(int n){// 假设n是正整数，这里不考虑0的阶乘
    if(n <= 2) return n;
    return f(n - 1) * n;
}

假设我们分别求3和4的阶乘，那么计算机的求解过程为：

f(3) = f(2) * 3 = 2 * 3 = 6;
f(4) = f(3) * 4 = f(2) * 3 * 4 = 2 * 3 * 4 = 24;

可以看到：

在求 f(4) 时有 f(4) = f(3) * 4，求 f(3) 时有 f(3) = f(2) * 3，也就是说当前问题的解可以由其子问题的解求出，这就是最优子结构性质。
求解 f(3) 需要求 f(2)，求 f(4) 也需要求 f(2)，这就是子问题重叠性质——在求 f(3) 和 f(4) 时都需要求解 f(2)。假如我们记录下已经求解过的 f(3) 和 f(2) 那么在求解 f(4) 时就可以使用f(3) 的值了，直接返回 f(4) = f(3) * 4 = 24 。
在求解 f(3) 时，已经计算了 f(2) 的值并由此得到了 f(3) 的值。而当求解 f(4) 时，又分别计算了 f(3) 和 f(2) 的值，

动态规划

承接上文的阶乘求解，使用递归方法我们会重复求解许多子问题，这会浪费大量的时间和栈资源，可能引发超时和爆栈的问题。因此我们可以使用数组在每一次求解过某一个问题时，就记录下它的解，那么在之后需要使用到该问题时，就可以直接取值而不用再递归到底求解咯。

int dp[10010];
void f(int n){
    // 通过dp数组就将每个数的阶乘值保存下来了
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++){
        dp[i] = i * dp[i - 1]; 
    }
}

这样的话，我们可以直接通过访问 dp[n] 来获得 n 的阶乘值。如此，不仅避免了重复求解相同的子问题，也不会出现递归爆栈的问题。以上问题是一个一维的动态规划问题，不过我们通常见到的是二维动态规划问题，即使用二维数组 dp[][]来记录答案。先不用着急知道二维的题目是啥样的，按顺序看下去，最后会在本文末尾的例题讲解中狠狠感受到滴。

三要素

截止到现在，我想你大概已经了解了动态规划是个什么东西。接下来，我们将一起来看看当使用动态规划求解某一个问题时，需要哪几个步骤（即求解模板）。

明确数组的含义，我们需要知道这个数组每个状态代表了什么意思，如上文的阶乘问题中 dp[n] 代表 n 的阶乘。个人觉得，这是相对较难的一步，因为对于动态规划而言，步骤都是一样的，直白点说就是填数组得到答案，但是如何建模数组，用数组去表示题目中的状态是以下两部的基础，尤其是第二步的找递推式。
找出数组元素之间的递推关系式，即原问题的解与其子问题的解之间的关系。依旧是看阶乘问题，这一步对应于找到 dp[i] = i * dp[i - 1];这一关系式，这一步也不简单。
找出初始值或者说是处理边界值，我们要为 dp 数组的部分元素位置进行初始化、赋初始值，如 dp[1] = 1; dp[2] = 2;。这一步也是为了保证我们访问数组时不会访问到不合理的位置或者无效的随机值。

以上这就是使用动态规划方法解决问题时的步骤，正确解决了以上三步，那也就意味着你离AC只差提交代码了！！

例题

首先，请uu们注意，即使是看完这篇文章并且全部掌握这里的每一句话，也会了接下来的例题，当你去刷动态规划的题目时，依旧会觉得难以上手这是很正常的。算法无易事，虽然我不喜欢鸡汤，但很多事情真的本身就是不容易做成的。无论是我们学习算法，还是日常生活学习中做其他事情，如果我们想做出点样子，唯有百炼成钢！

“往往有这种情形，有利的情况和主动的恢复，产生于再坚持一下的努力之中”，伟大的教员如是说。不要去怀疑自己的努力和能力，慢慢来，会开花，也会结果的。

青蛙跳台阶

问题描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

这是一个不算难的经典题目，如果你是第一次接触动态规划，可以自己按照上面提到的三个步骤做一下。

思路分析

明确数组的含义：题目读罢，我们应该能反应过来，可以使用数组来表示 “跳上一个n级台阶的总跳法数” ，因为只有一个变量 n，很自然有 dp[n] —— 青蛙跳上第 n 级台阶的跳法数。
找出数组元素之间的递推关系式：由题意可知，青蛙一次可以跳上1级台阶，也可以跳上2级台阶。那么我们考虑如果青蛙要跳到第 n 阶台阶，它只有两种可能：从第 n-1 阶跳 1 阶到第 n 阶，或者从第 n-2 阶跳 2 阶到第 n 阶，因此我们可以得到 dp[n] = dp[n-1] + dp[n-2]。
边界处理：由递推式我们可以知道，需要对 dp[1] 和 dp[2] 进行初始化，令 dp[1] = 1，dp[2] = 1。（这里假定 n 为正整数，不考虑0）。

uu们可以自行分析该问题的最优子结构性质和子问题重叠性质。

核心代码

int f(int n){
    dp[1] = 1;
    dp[2] = 2;
    for(int i = 3; i <= n; i++){
        dp[i] = dp[i -1] + dp[i - 2];
    }
    // dp[n] 即为最终结果
}

力扣传送门——70. 爬楼梯 - 力扣（LeetCode）

以下是我在力扣AC的代码，简单的解释一下：我们知道递推式为dp[i] = dp[i -1] + dp[i - 2]，也就是说当我们在求某一层阶梯的方法数时，只用到了前边两层阶梯，既然如此，那么我们就可以只使用两个变量来记录这两个值，并在每一轮的过程中进行更新。

这其实是动态规划的优化（时间复杂度不变，对空间复杂度进行优化），之后会再单独拿例题来给大家分享一维、二维的优化。不过建议uu们可以先使用咱上边的一维动态规划方法来解决，尤其是对于刚接触动态规划的uu来说，先练习普通动态规划方法，优化不着急掌握的，就像是先学走路再学跑步，慢慢来，会更快！

class Solution {
public:
    int climbStairs(int n) {
        int a = 1, b = 2;
        int c = 0;
        if(n <= 2) return n;
        for(int i = 3; i <= n; i++){
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
};

0-1 背包问题

背包问题是动态规划里非常经典的题目，一如一位伟大的哲学家曾言，“如果你不知道 0-1 背包问题，那你就相当于没学过动态规划”，啧啧，箴言！！

0-1背包问题：给定 n 种物品和一背包。物品 i 的重量是 w ，其价值为 v ，背包的容量为 c 。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

在选择装入背包的物品时，对每种物品只有两种选择，即装入背包或不装入背包。不能将物品 i 装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。

思路分析

最优子结构

这里我们先一起分析0-1背包问题的最优子结构性质：
$0,w_i > 0,v_i > 0 ( 1 ≤ i ≤ n ),要求找出一个 n 元 0-1 向量(x_1,x_2,…,x_n)，\\其中x_i∈\{0,1\} ，0代表不选，1代表选(1 ≤ i ≤ n)，使得\sum_{i=1}^{n}{w_ix_i}\leq c 而且使得\sum_{i=1}^{n}{x_iv_i}达到最大$
由于公式太难敲了（比如求和公式呜呜），为了节约时间，我翻了我们学校几本讲到0-1背包问题的教材，找了一个讲的最清晰的截图放在了这里，请uu们笑纳

在这里插入图片描述

寻找递推式

过程略显抽象，可以先看完一遍该三个步骤，再结合着下方的AcWing实际题目举例一起看。

在以上的分析中，我们知道对于每一个物品都只有两种情况，放进背包（在最优解中）或者不放进背包（不在最优解中）。很自然的，我们应该遍历一遍所有物品，分别考虑它们的情况。
我们可以考虑到一件物品是不是可以放进背包的先决条件是背包当前的容量是不是大于该物品的体积：如果当前背包的可用容量小于物品的体积很显然不能放进背包；而如果当前背包可用容量大于物品体积，那么我们要考虑为了最终能获得最大价值——是把当前物品放进背包获得的价值更大还是不将该物品放进背包获得的价值大。比如，有两个物品a和b，第一个物品a的体积为1，价值为2；第二个物品b的体积为2，价值为1。假设此时我们遍历到物品b，背包容量为2，很显然我们只放a不放b获得的价值更大。

由此，我们可以考虑构造一个二维数组dp[][]，第一维考虑物品，第二维从0到c考虑背包容量，对于dp[i][j]代表考虑到第 i 个物品，背包可用容量为 j 时可以获得的最大价值。如果你是首次接触0-1背包问题，那么觉得以上这段话抽象是再正常不过的，不要着急，结合着下边的例题多看两遍，你肯定会掌握的！
由2得到递推式（考虑到公式难敲，我就手写了哈兄弟们，望体谅）：

在这里插入图片描述

举例

acwing背包问题传送门 —— 2. 01背包问题 - AcWing题库，兄弟们学完后可以自己敲一下在该链接中提交。

我们在这就使用AcWing题目中的数据，有4个物品，背包容量为5，4个物品的体积、价值数据如表格所示：

物品标号(i)	1	2	3	4
体积(w[i])	1	2	3	4
价值(v[i])	2	4	4	5

二维表格dp的填表过程：

对表格的第一列第一行初始化为0
考虑第一个物品，背包容量为0时，能获得的最大价值为0，背包容量为1~5时，物品1可以放进背包，获得的最大价值为2
遍历到第二个物品，背包容量为0时，两个物品都无法放进背包，价值为0；背包容量为1时，物品1可以放进背包，价值为2；背包容量为2时，此时物品2有放进背包的可能，此时考虑要不要放进，由递推公式可知，选择只放进物品2，获得的价值较大为4；当背包容量为3~5时，物品1和物品2都放进背包时有最大价值6.

在这里插入图片描述

表格剩下的两行就留给兄弟们自己根据递推公式填上了，填完后可以讲下方打印表格的代码片段取消注释，把表格打印出来后和自己填的答案对一对。

代码实现

以下代码已在AcWing提交并通过，请uu们放心食用

#include<bits/stdc++.h>
using namespace std;
const int N = 1007;
int dp[N][N] = {0};
// w[]存每个物品的体积，v[]存储每个物品的价值
int w[N] = {0}, v[N] = {0};
int num, vol; // num是物品个数，vol是背包的体积
int main() {
	scanf("%d%d", &num, &vol);
	for (int i = 1; i <= num; i++) {
		scanf("%d%d", &w[i], &v[i]);
	}
	for (int i = 1; i <= num; i++) {
		for (int j = 1; j <= vol; j++) {
			dp[i][j] = dp[i - 1][j];
			if (j >= w[i]) {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
			}
		}
	}
//	// 打印出来整个表格 
//	for(int i=0;i<=num;i++){
//		for(int j=0;j<=vol;j++){
//			printf("%d ", dp[i][j]);
//		}
//		printf("\n");
//	}
	printf("%d", dp[num][vol]);
	return 0;
}
/*4 5
1 2
2 4
3 4
4 5
output: 8*/