蓝桥杯高频考点——经典01背包问题详解（附例题）

前言

起初我真的真的觉得动态规划是非常难的东西 以至于到现在我才鼓起勇气去真正的学它 但其实只要我们沉下心来分析 知道我们每一步要干嘛 好像也没有那么的难以理解了 其实我倒觉得
从最直白的DFS——>记忆化搜索（用一个memo[ ]数组来减少不必要的计算）——>dp数组（背包问题）
我觉得这是一个比较好的路径 但可惜我并没有花很多时间去练习 以至于有些DFS我都AC不了 但好在都能及时改正 现在看来真的是得益于合理的学习路径和优质的视频讲解 感恩
等过一段时间我会把所有东西都做一个开源 以供后续0基础读者能够安稳的起步
不为什么 只想把前辈们给我打的伞传递下去！

小明的背包

题目链接

思路详解

可以说这是一个非常经典的背包问题 需要借助我们的dp（Dynamic Programming）来解决
没什么难的 只不过是你还不知道

• 1 首先我们需要明确 在这题里面什么是状态和选择

状态是可能变化的量 即包的剩余容量以及可以选择的物品
选择就是引起状态改变的量 即拿或者不拿 当前的物品

• 2 其次我们需要明确我们dp数组的定义

什么是dp数组 就是我们用这个数组来表达某一种状态
例如 在这题中dp[3][2]=6 他的意思就是说
如果只考虑前三件物品 在背包容量为2的情况下 可以拿到的最大价值是6
我的理解：
可以与数学里面的线性规划来理解 就像是有两个限制（两条线）
而你需要找到在这个限制之下的函数最值F（x）可能我说的不够准确 但是我确实是这么来理解的
同时这意味着 ：
我们dp数组的维度也就是dp后面跟几个方括号 [ ] 跟我们的状态有关 也就是说 这些状态的变化会引起最值的波动

好了 那么这题中 dp[i][w] 的定义就是：
对于前i件物品 当背包容量为w时的最大价值

• 3 最后我们需要根据状态写出状态转移方程
• 我们无非就是两个选择 选或者不选

1.不选 我们根据这题dp数组的定义就是 ：

即对于当前这件物品的价值不用考虑 但前i-1件物品还是在包里的
所以：对于前i件物品 我们不装i 当背包容量为w时的最大价值为：

dp[i][w]=dp[i-1][w]

2.选 (难点)
选的话 假设包的容量够放当前的物品
那么首先 在最终价值当中 肯定包含第i件物品 即val[i]
其次 我们只需要知道在剩余的背包容量为w-wt[i]（总的容量减去第i件物品的容量）情况下前i-1件物品的最大价值是多少
因此我们可以再次根据dp数组的定义得到：

dp[i-1][w-wt[i]]

想要知道当前状态下的最大价值dp[i][w] 我们只需要对上述求个和就可以 即：

dp[i][w]=dp[i-1][w-wt[i]]+val[i]

那么这道题就迎刃而解了

视频资源（必看）：

对于动态规划的核心思路

满分代码

需要调整的细节就是我们遍历的起点是1 而wt和val的起始下标是从0开始的 所以在循环中 wt数组和val数组需要进行偏移1
另外 这个work函数实际上并不需要任何参数 如果你把n和v定义成全局变量 我只不过调试的时候给他加到main函数里了
其余的完全就是按照上面的思路来的

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int wt[N],val[N];
int dp[N][N];
int work(int n,int v)
{//遍历所有组合 for(int i=1;i<=n;i++){for(int w=1;w<=v;w++){//当前状态下装不下第i件物品 只能选择不装if(w-wt[i-1]<0){dp[i][w]=dp[i-1][w];}else{dp[i][w]=max(dp[i-1][w],dp[i-1][w-wt[i-1]]+val[i-1]);//取最优 因为要考虑性价比问题 }}}return dp[n][v];
}
int main()
{int n,v;cin>>n>>v;for(int i=0;i<n;i++){cin>>wt[i]>>val[i];}memset(dp,0,sizeof(dp));//初始化 //basecase dp[0][w]=0 dp[i][0]=0int res=work(n,v);cout<<res<<endl;return 0;
}

编辑距离

题目链接

思路详解

labuladong讲的太好了

AC代码

class Solution {
public:int minDistance(string s1, string s2) {int m = s1.size(), n = s2.size();// i，j 初始化指向最后一个索引return dp(s1, m - 1, s2, n - 1);}private:// 定义：返回 s1[0..i] 和 s2[0..j] 的最小编辑距离int dp(string &s1, int i, string &s2, int j) {// base caseif (i == -1) return j + 1;if (j == -1) return i + 1;if (s1[i] == s2[j]) {// 啥都不做return dp(s1, i - 1, s2, j - 1);}return min({// 插入dp(s1, i, s2, j - 1) + 1,// 删除dp(s1, i - 1, s2, j) + 1,// 替换dp(s1, i - 1, s2, j - 1) + 1});}
};

优化

class Solution {
private:// 备忘录vector<vector<int>> memo;int dp(string& s1, int i, string& s2, int j) {if (i == -1) return j + 1;if (j == -1) return i + 1;// 查备忘录，避免重叠子问题if (memo[i][j] != -1) {return memo[i][j];}// 状态转移，结果存入备忘录if (s1[i] == s2[j]) {memo[i][j] = dp(s1, i - 1, s2, j - 1);} else {memo[i][j] = min3(dp(s1, i, s2, j - 1) + 1,dp(s1, i - 1, s2, j) + 1,dp(s1, i - 1, s2, j - 1) + 1);}return memo[i][j];}int min3(int a, int b, int c) {return min(a, min(b, c));}public:int minDistance(string word1, string word2) {int m = word1.size(), n = word2.size();// 备忘录初始化为特殊值，代表还未计算memo = vector<vector<int>>(m, vector<int>(n, -1));return dp(word1, m - 1, word2, n - 1);}
};