b站视频
💡 Tips：求有限集中的最值
01背包
朴素写法
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i ++ ){
for (int j = 0; j <= m; j ++ )
{
f[i][j] = f[i - 1][j]; // 左半边的子集
if (j >= v[i])
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
}
cout << f[n][m] << endl;
return 0;
}
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/249968/
来源：AcWing
优化空间之后的写法
怎么说呢，就是原来第二个算式是f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])，注意f[i - 1][j - v[i]]，需要i-1,也就是前一个。
要是从左往右边算的话，✨（假如我们来到了第四行，正在计算f[5]需要用到f[4]的数据），f[4]会先于f[5]的数据被更新，也就是f[5]中存的还是第3行的数据，而f[4]中已经是第4行的数据，所以不满足f[i - 1][j - v[i]]中的i-1。
要是从右往左边算的话，✨（假如我们来到了第四行，正在计算f[5]需要用到f[4]的数据），f[5]会先于f[4]的数据被更新，f[4]中依然是第3行的数据，此时f[5]可以通过f[4]（第3行的数据）计算，满足f[i - 1][j - v[i]]中的i-1。
😘下面的完全背包的优化也是如此
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i ++ )
for (int j = m; j >= v[i]; j -- )
f[j] = max(f[j], f[j - v[i]] + w[i]);
//当你从小到大枚举j时，f[ j - v[i] ] 会在f[ j ] 之前被枚举到，,而从大到小枚举j时，在此枚举后，f[ j - v[i] ] 从原来的f[i-1][j-v[i]] 更新成了f[i][j-v[i]]，,f[j]一定会先与f[j-v[i]]枚举到，此时f[j-v[i]]依旧是f[i-1][j-v[i]]
cout << f[m] << endl;
return 0;
}
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/249968/
来源：AcWing
完全背包
💡 Tips：推导公式
f ( i , j ) = m a x ( f ( i − 1 , j ) ， f ( i − 1 , j − v i ) + w i ， f ( i − 1 , j − 2 v i ) + 2 w i ， . . . . . . ) f ( i , j − v i ) = m a x ( f ( i − 1 , j − v i ) ， f ( i − 1 , j − 2 v i ) + w i ， f ( i − 1 , j − 3 v i ) + 2 w i ， . . . . . . ) f ( i , j ) = m a x ( f ( i − 1 , j ) ， f ( i , j − v i ) + w i ) f(i,j)=max(f(i-1,j)，f(i-1,j-v_i)+w_i，f(i-1,j-2v_i)+2w_i，......)\\ f(i,j-v_i)=max(f(i-1,j-v_i)，f(i-1,j-2v_i)+w_i，f(i-1,j-3v_i)+2w_i，......)\\ f(i,j)=max(f(i-1,j)，f(i,j-v_i)+w_i) f(i,j)=max(f(i−1,j)，f(i−1,j−vi)+wi，f(i−1,j−2vi)+2wi，......)f(i,j−vi)=max(f(i−1,j−vi)，f(i−1,j−2vi)+wi，f(i−1,j−3vi)+2wi，......)f(i,j)=max(f(i−1,j)，f(i,j−vi)+wi)
朴素写法
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
f[i][j] = f[i - 1][j];
//f[j] = f[j];先算右边，是上一层的
if (j >= v[i])
f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
//f[j] = max(f[j], f[j - v[i]] + w[i]);
//在算f[j]的时候，f[j - v[i]]已经被算出来了，就是第i层的
}
cout << f[n][m] << endl;
return 0;
}
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/250029/
来源：AcWing
优化空间之后的写法
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i ++ )
for (int j = v[i]; j <= m; j ++ )
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/250029/
来源：AcWing
对比
//01背包
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
//完全背包
f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
区间DP问题
设有N堆石子排成一排，其编号为1，2，3，…，N。每堆石子有一定的质量，可以用一个整数来描述，现在要将这N堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻合并时由于选择的顺序不同，合并的总代价也不相同。
例如有4堆石子分别为 1352，我们可以先合并1、2堆，代价为4，得到4 5 2，又合并 1，2堆，代价为9，得到92，再合并得到11，总代价为4+9+11=24;
如果第二步是先合并2，3堆，则代价为7，得到4 7，最后一次合并代价为11，总代价为4+7+11=22.
问题是:找出一种合理的方法，使总的代价最小，输出最小代价。
输入格式
第一行一个数N表示石子的堆数N。
0第二行N个数，表示每堆石子的质量(均不超过1000)。
输出格式
输出一个整数，表示最小代价。
数据范围
1 <N < 300
输入样例
4
1 3 5 2
输出样例
2
#include <iostream>
using namespace std;
const int N = 310;
int n;
int s[N]; // 前缀和
int f[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> s[i], s[i] += s[i - 1];
for (int len = 2; len <= n; len ++ )//区间长度
for (int i = 1; i + len - 1 <= n; i ++ )//左端点
{
int j = i + len - 1;//右端点
f[i][j] = 1e8;
for (int k = i; k < j; k ++ )
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
}
cout << f[1][n] << endl;
return 0;
}
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/250070/
来源：AcWing
前缀和
一维前缀和：有一个一维数组 x 和该数组的一维前缀和数组 y ，则 x 和 y 满足以下关系：
y
0
=
x
0
、
y
1
=
x
0
+
x
1
、
y
2
=
x
0
+
x
1
+
x
2
、
…
…
y
n
=
x
0
+
x
1
+
x
2
+
…
+
x
n
y_0=x_0、y_1=x_0+x_1、y_2=x_0+x_1+x_2、……y_n=x_0+x_1+x_2+…+x_n
y0=x0、y1=x0+x1、y2=x0+x1+x2、……yn=x0+x1+x2+…+xn文章来源：https://www.toymoban.com/news/detail-861784.html
s[1] = a[1] ;
s[2] = a[1] + a[2] ;
s[3] = a[1] + al2] +a[3] ;
....
s[i] = a[1] + a[2] + a[3] + ......+ a[i];
最长公共子序列
文章来源地址https://www.toymoban.com/news/detail-861784.html
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main()
{
cin >> n >> m >> a + 1 >> b + 1;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (a[i] == b[j])
f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
cout << f[n][m] << endl;
return 0;
}
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/250113/
来源：AcWing
到了这里，关于动态规划-闫氏老方!中华老字号（DP笔记）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
