概述
写在开头：
这篇博客将从最开始入门到提升，说明关于如何学习动态规划，适合小白以及学过想要提高的选手，篇幅可能较长持续更新，主要是为了带学弟学妹以及自己复习而写。
由于时间和篇幅等问题，一些基础的东西将不会在本博客讲解，但放有相关学习资源和学习途径，大家可以根据自己的需要进行仔细的学习每个部分然后在返回本博客跟着学下去。
大家可以根据自己的需要进行学习，好了废话不多说还是直接开始吧！
文章目录
- 入门
- 数字三角
- 递归分析
- 递推分析
- 解决动态规划的一般思路
- 建议学习地址
- 动态规划之线性DP
- 理解
- 最长上升子序列
- 基础代码
- 终极代码
- 最长公共子序列
- 代码
- 最大子段和
- 最长不重复子段
- 动态规划之背包问题
- 01背包
- 理解（基础学习按这里）
- 朴素代码
- 终极代码
- 完全背包
- 理解
- 朴素代码
- 进阶代码
- 终极代码
- 多重背包
- 理解
- 朴素代码
- 进阶代码
- 终极代码
- 分组背包
- 理解
- 解决代码
- 动态规划之区间DP
- 石子合并
- 理解
- 代码
入门
要想学好动态规划首先要学好递归与递推，在此基础上才能进阶到动态规划，这个步骤是怎么来的呢？
先别急，首先我们要明白一个概念
我们写的递归程序其实就像我们的深度优先搜素（不理解的可以先去学学，不学也可以只是帮助理解，后面内容用不到），也就是深度遍历？
什么是深度遍历呢？也就是不到底咋们就不回头；
然而我们没有剪枝的递归程序也有一个特点，那就是不走完不罢休啊；
这些怎么理解呢？
下面，我们先看一道题目：
数字三角
ps:这是选自蓝桥杯竞赛的真题
问题描述
（图３.１－１）示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路
径，使该路径所经过的数字的总和最大。
●每一步可沿左斜线向下或右斜线向下走；
●1＜三角形行数≤100；
●三角形中的数字为整数0，1，…99；
（图３.１－１）
输入格式
文件中首先读到的是三角形的行数。
接下来描述整个三角形
输出格式
最大总和（整数）
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30
递归分析
我们从（i,j）开始走只能走到（i+1,j）或者（i+1,j+1），对于（i,j），我们需要从后面两个和当中选择较为大的一个加上此时(i,j)的值就可以得到（i,j）的最优解，所以，我们只需要采用深度遍历的思想进行递归每条路径就可以得到答案。
伪代码：
int maxsum(int i,int j){
if(i==n) return a[i][j];
int x=maxsum(i+1,j),y=maxsum(i+1,j+1);
return max(x,y)+a[i][j];
}
这样没有什么问题，我们的程序也非常的简单，几行代码就可以完成。
但是它真的好吗？
我们来分析一下：对于每一个（i,j）我们都要搜寻它的后面两个数，然而这两个数不一定只被搜寻一次，我们每一次深度遍历只要需要判断它是不是在最优路径上，它就需要被搜寻一次，具体什么意思呢？
7(1)
3(1) 8(1)
8(1) 1(2) 0(1)
2(1) 7(3) 4(3) 4(1)
4(1) 5(4) 2(6) 6(4) 5(1)
小括号里面就是每个数字被调用的次数，大家可以根据程序自己手动跑一边理解，你就能理解我们的不减枝递归的不到底不停和不走完不罢休的原理了。
我们很容易发现这样的程序有一个问题，就是有大量的重复计算，那有没有改进呢？
有啊，既然有重复计算，那我们就把已经计算好了的数存在数组里面，就不再考虑了嘛，这不就避免了吗？
没错，这一步操作就是剪枝，我们可以开一个再二维数组来存已经算过的程序，二维数组初始化为-1，因为数字有0的情况，核心代码：
手动初始化为-1，代码省略了哈
int maxsum[1086][1086];
int maxsum(int i,int j){
if(maxsum[i][j]!=-1) return maxsum[i][j];
if(i==n) return a[i][j];
int x=maxsum(i+1,j),y=maxsum(i+1,j+1);
maxsum[i][j]=max(x,y)+a[i][j];
return maxsum[i][j];
}
不过，我们其实也可以用递推来解决这个题
递推分析
我们将问题转换简单一点，如果题目只是问
7
3 8
最大值，那我们可以立马得出只需要将7+8就可以了
如果原问题是
7
3 8
8 1 0
我们可以发现8+3=11,1+8=9，而11>9,所有7+11=18，最优路径就是8+3+7=18
发现了吗？好像我们每次只需要选那一个数字后面两个中最大的就可以了?
你可以继续写下去试试
…
于是，我们可以从最底下开始递推，我们知道对于(i,j)，我们只需要选择它底下两个中最优的那一个就可以了，那我们不妨从倒数第二排开始，对于它底下的两个数我们只需要选择最大的那个加上此时（i,j）的值那一定就是最优的情况，这样递推到最顶层，就是我们想要的答案了。
也就是——
30
23 21
20 13 10
7 12 10 10
4 5 2 6 5
空间优化：我们发现在这个思路下，我们甚至不用多开数组去记录我们已经算出的答案，只需要在原二维数组中改为我们最优后的答案。
核心代码：
for(int i=n-1;i>=1;i--)
for(int j=1;j<=i;j++)
maxsum[i][j]=a[i][j]+max(a[i+1][j],a[i+1][j+1]);
其实，甚至二维数组也不需要，直接一维都可以，怎么写留给大家思考啦！~
解决动态规划的一般思路
1.将原问题转换为子问题
比如上面那个例子，我们将原来的问题转换成小问题来考虑，这样就能更直观地看到问题原来的样子，只要我们把子问题解决，原问题也能被解决。
并且，子问题一旦被求出就可以被保存
2.确定状态关系
比如三角那题，（i,j）的最优解就是a[i][j]加上它下面两个数的最优解
3.确定初始状态和边界值
比如上面那题初始状态就是底边数
4.确定状态转移方程
也就是找到数据间的关系表达式，我们会在后面慢慢练习，这是动态规划的核心
建议学习地址
1.acwing算法基础课堂（付费）
2.中国大学慕课的北京大学程序设计与算法（二）算法基础（免费）
3.B站搜索相关知识点就可以看相关视频讲解（免费）
4.CSDN学习博客（免费）
PS:大家可以多个地方进行学习理解，如果一个地方感觉理解不够就可以去其他地方学习理解，从不同角度进一步理解，只要理解了就可以了，不必执着于多看，重点在理解多练。
动态规划之线性DP
线性DP是指推到的过程是线性的，什么意思呢？下面来感受一下：
理解
有一篇讲得比较好的博客可以进一步理解：按题解
可恶，刚才敲的电脑关机全没了，我的博客啊…
算了， 心态超级好，重新来吧。。。
最长上升子序列
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤1000，
−109≤数列中的数≤109
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4
题解：
只需要算出当前数之前所有的数最大上升子序列就可以算出当前数的最大上升子序列。
基础代码
#include<iostream>
using namespace std;
int a[10086],f[10086];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int ans=0;
for(int i=0;i<n;i++){
f[i]=1;
for(int j=0;j<i;j++)
if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);
ans=max(ans,f[i]);
}
cout<<ans;
return 0;
}
问题二：
我们很容易算出来时间复杂度是O（n^2)，在问题二中时间就爆表了！有没有办法可以提高呢？
既然在这里说了，那肯定是有的啦！
我们再来看看样例：
3 1 2 1 8 5 6
第一轮：3
第二轮；1
第三轮：1 2
第四轮：1 2
第五轮：1 2 8
第六轮：1 2 5
第七轮：1 2 5 6
我们发现，对于同样长度的子串，它的末端越小越好，因为这样以后就也有更多机会拓展。
我们发现我们的答案是递增的单调栈，那我们只需要用单调栈来进行维护就好了：
1.如果栈顶小于当前数，入栈
2.如果不小于，那么我们查找当前数在栈中大于等于a[i]的那个数进行替换，达到单调栈末端最小要求（因为我们只需要记录栈的长度，而即使前面小的数被后面的替换了也没有关系）
终极代码
#include<iostream>
#include<stack>
using namespace std;
int a[100086],stk[100086];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int len=0;
stk[++len]=a[0];
for(int i=1;i<n;i++){
if(a[i]>stk[len]) stk[++len]=a[i];
else{
//二分查找，不然要超时
int k=lower_bound(stk+1,stk+1+len,a[i])-stk;
stk[k]=a[i];
}
}
cout<<len;
return 0;
}
最长公共子序列
给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数 N 和 M。
第二行包含一个长度为 N 的字符串，表示字符串 A。
第三行包含一个长度为 M 的字符串，表示字符串 B。
字符串均由小写字母构成。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N,M≤1000
输入样例：
4 5
acbd
abedc
输出样例：
3
题解：
这题如果想不到，其实有个小技巧，写一个二维数组，写出第一个序列每一位对应着第二个序列每一位的答案，很清楚就能看出答案，当两个元素不相等的时候，取f[i-1,j]或者f[i,j-1]较大值，如果相等则取f[i-1][j-1]+1;
代码
#include<iostream>
#include<stack>
using namespace std;
int f[1086][1086];
int main(){
int n,m;
cin>>n>>m;
char s1[1086],s2[1086];
cin>>s1+1>>s2+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(s1[i]==s2[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
}
}
cout<<f[n][m];
return 0;
}
最大子段和
链接：https://www.nowcoder.com/questionTerminal/03d341fb6c9d42debcdd38d82a0a545c
来源：牛客网
输入一个整形数组（可能有正数和负数），求数组中连续子数组（最少有一个元素）的最大和。要求时间复杂度为O(n)。
输入描述:
【重要】第一行为数组的长度N（N>=1）
接下来N行，每行一个数，代表数组的N个元素
输出描述:
最大和的结果
示例1
输入
8
1
-2
3
10
-4
7
2
-5
输出
18
说明
最大子数组为 3, 10, -4, 7, 2
解题思路：
在这里插入图片描述
#include<stdio.h>
const int N=110;
int a[N];
int sum,i,n,b=0;
int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&a[i]); //输入数据
}
for(i=1;i<=n;i++){
if(b<0){
b=a[i];
}else{
b+=a[i];
}
if(sum<b) {
sum=b;
}
}
printf("%dn",sum);
return 0;
}
最长不重复子段
理解了上面，下面我们可以直接进入动态规划的学习了。
动态规划之背包问题
01背包
题目描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8
理解（基础学习按这里）
找到子问题的最优解，然后推出原问题的最优解，关键就是找到关系写出状态转移方程。
关系就是f(i,j)当前的第i个物品选与不选，要选出从前i个物品中总体积<=j的最大值
状态转移方程：
d
p
[
i
]
[
j
]
=
m
a
x
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
−
1
]
[
j
−
v
[
i
]
]
+
w
[
i
]
)
{dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])}
dp[i][j]=max(dp[i−1][j],dp[i−1][j−v[i]]+w[i])
条件：
j
−
v
[
i
]
>
=
0
{j-v[i]>=0}
j−v[i]>=0，即当前物品可以放到背包里面去。
状态转移方程：
d
p
[
i
]
[
j
]
=
d
p
[
i
−
1
]
[
j
]
{dp[i][j]=dp[i-1][j]}
dp[i][j]=dp[i−1][j]
条件：
j
−
v
[
i
]
<
0
{j-v[i]<0}
j−v[i]<0，即当前物不品可以放到背包里面去。
朴素代码
#include<iostream>
using namespace std;
int n,k;
const int N=1100;
int v[N],w[N];
int dp[N][N];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
dp[i][j]=dp[i-1][j];
if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
}
}
cout<<dp[n][k];
return 0;
}
终极代码
我们来仔细想想，对于dp[i-1][j]这一层，我们是不是其实只用到了它上一层的数据，也就是我们需要保存的数据也就只是上一层的。
于是我们进行下面修改：
for(int i=1;i<=n;i++){
for(int j=v[i];j<=k;j++){
if(j>=v[i]) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
但是真的对吗？
如果我们依然根据核心代码从0~m枚举的话，对于dp[j-v[i]]其实是已经计算过了，也就是其实等于dp[i][j-v[i]]而不是我们要的dp[i-1][j-v[i]]，解决这个办法其实我们只需要将枚举的顺序改变一下，也就是逆序，从大到小枚举从而解决小的先被枚举完。
#include<iostream>
using namespace std;
int n,k;
const int N=1100;
int v[N],w[N];
int dp[N];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++){
for(int j=k;j>=v[i];j--){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout<<dp[k];
return 0;
}
完全背包
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10
理解
重点在于集合的划分
找到子问题不必多说，关键是对于第i个物品我们有不选和选1~k个
即0~k。
其他都思考和01背包一模一样
状态转移方程：
d
p
[
i
]
[
j
]
=
m
a
x
(
d
p
[
i
]
[
j
]
,
d
p
[
i
−
1
]
[
j
−
k
∗
v
[
i
]
]
+
k
∗
w
[
i
]
)
{dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i])}
dp[i][j]=max(dp[i][j],dp[i−1][j−k∗v[i]]+k∗w[i])
(对不住了Y总，不是有意把表情截下来的）
朴素代码
#include<iostream>
using namespace std;
int n,k;
const int N=1100;
int v[N],w[N];
int dp[N][N];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
for(int k=0;k*v[i]<=j;k++)
dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
}
}
cout<<dp[n][k];
return 0;
}
进阶代码
当然，上面这样做会超时，我们来看看如何提升我们的算法。
写出f[i][j]和f[i][j-v[i]]，我们可以发现对于f[i][j]后面的那一堆，是等于f[i][j-v]+w的，我们选所有答案中最大的那一个。
（PS：这里每次多出的数据都是在前面多出，并在前面加入，记住这一点）
那么也可也变成了01背包的理解，要么选第i个物品要么不选。简化一下：
这样时间复杂度就只有O（n^2)
#include<iostream>
using namespace std;
int n,k;
const int N=1100;
int v[N],w[N];
int dp[N][N];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
dp[i][j]=dp[i-1][j];
if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
}
}
cout<<dp[n][k];
return 0;
}
终极代码
融会贯通，我们来对比一下01背包和完全背包，来进一步理解。
我们发现01背包和完全背包唯一的不同就是：
对于v[i]<=j时，01背包是取自i-1层，而完全背包是取自i层，虽然只差了一点点，但是其中的思考确实大不相同的。
01背包是对第i-1层的回溯寻找最优解，完全背包是对第i层回溯寻找最优解，造成这样的差别在于01背包物品只有唯一一个，要么选要么不选，我们只需要考虑上一层就好，这个思维其实只是一维思维；
而完全背包物品是无限的，所以对于第i层j空间，我们需要考虑上一层（不选的时候），和这一层j空间两个（选的时候），因为对于这一层的每个空间来说也是一次动态规划，其实也是也就是二维思维了，建议搞不太清楚的可以自己写个二维数组表来看一看。
由于是对于第i层，我们需要前面j-1已经动规过的数据，所以我们进行顺序
#include<iostream>
using namespace std;
int n,k;
const int N=1100;
int v[N],w[N];
int dp[N];
int main(){
cin>>n>>k;
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<=k;j++){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout<<dp[k];
return 0;
}
多重背包
多重背包问题 I
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤100
0<vi,wi,si≤100
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10
理解
对于第i个物品我们有不选和选1~s[i]个
朴素代码
#include<iostream>
using namespace std;
int n,k;
const int N=1100;
int v[N],w[N],s[N];
int dp[N][N];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
for(int k=0;k*v[i]<=j&&k<=s[i];k++)
dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
}
}
cout<<dp[n][k];
return 0;
}
多重背包问题 II
进阶代码
还是老话，太耗时间了，可以用完全背包的思路来优化吗？
我们写出表达式：
我们发现后面多了一项，这怎么办呢？
这里有给办法——二进制优化
可以用0~512凑到0至023
也就是可以：
怎么写呢？
#include<iostream>
using namespace std;
int n,k;
const int N=250000;
int v[N],w[N],s[N];
int dp[N];
int main(){
cin>>n>>k;
int cnt = 0;
for(int i=1;i<=n;i++){//二进制优化
int a,b,s;
cin>>a>>b>>s;
int k=1;
while(k<=s){
cnt++;
v[cnt]=a*k;
w[cnt]=b*k;
s-=k;
k*=2;
}
if(s){//剩下没有拆分的，比如17->17-1-2-4-8=2
cnt++;
v[cnt]=a*s;
w[cnt]=b*s;
}
}
n = cnt;
for(int i=1;i<=n;i++){
for(int j=k;j>=v[i];j--){//转换成01背包
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout<<dp[k];
return 0;
}
终极代码
多重背包问题 III
如果数据范围更大
就算用二进制依然会超时，怎么办呢？
我们重新回到一开开始
也就是这里来，我们当时是发现（i,j）对于（i,j-v）前面多了一个数，后面少了一个数，有没有发现它其实非常像我们的滑动窗口一样，窗口大小是s[i]，每次需要求窗口内的最大值。当然每次的数都在改变
那我们就可以用单调队列来模拟啦~
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=20010;
int f[maxn],g[maxn],q[maxn];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
memcpy(g,f,sizeof(f));
int v,w,s;//体积、价值、件数
scanf("%d%d%d",&v,&w,&s);
//按照体积分为v类,每个类起点为0,1,....v-1
for(int j=0;j<v;j++)
{
int head=0,tail=-1;
//遍历整个类
for(int k=j;k<=m;k+=v)
{
//利用单调队列滑动窗口
if(head<=tail&&k-s*v>q[head]) head++;//队首元素,不在于滑动窗口,踢出队首元素
//将在滑动区间内,中最大值,也就是单调队列中队首元素
if(head<=tail) f[k]=max(g[k],g[q[head]]+(k-q[head])/v*w);//01背包动态转移方程
//如果队尾元素小于g[k],则从队尾出队
while(head<=tail&&g[k]>=g[q[tail]]+(k-q[tail])/v*w) tail--;
//g[k]入队
q[++tail]=k;
}
}
}
printf("%dn",f[m]);
return 0;
}
分组背包
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。
接下来有 N 组数据：
每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤100
0<Si≤100
0<vij,wij≤100
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例：
8
理解
从第i组里面选第k个或者不选
和前面的大同小异
口诀：如果我们用的是i-1层那就从大到小倒序枚举，如果我们用的是第i层就从小到大顺序枚举。
解决代码
#include<iostream>
#include<algorithm>
using namespace std;
int n,k;
const int N=1100;
int v[N][N],w[N][N],s[N];
int dp[N];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>s[i];
for(int j=1;j<=s[i];j++)
cin>>v[i][j]>>w[i][j];
}
for(int i=1;i<=n;i++){//对于第i组
for(int j=k;j>=0;j--){//体积为j时，由于要用的是i-1层，所以倒序
for(int k=1;k<=s[i];k++)//第k个物品时
if(j>=v[i][k]) dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);
}
}
cout<<dp[k];
return 0;
}
动态规划之区间DP
石子合并
设有 N 堆石子排成一排，其编号为 1，2，3，…，N。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
例如有 4 堆石子分别为 1 3 5 2， 我们可以先合并 1、2 堆，代价为 4，得到 4 5 2， 又合并 1，2 堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=24；
如果第二步是先合并 2，3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22。
问题是：找出一种合理的方法，使总的代价最小，输出最小代价。
输入格式
第一行一个数 N 表示石子的堆数 N。
第二行 N 个数，表示每堆石子的质量(均不超过 1000)。
输出格式
输出一个整数，表示最小代价。
数据范围
1≤N≤300
输入样例：
4
1 3 5 2
输出样例：
22
理解
找到将i,j一分为二得到答案最小的那个k
代码
#include<iostream>
#include<algorithm>
using namespace std;
int a[400];
int f[400][400];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
for(int i=2;i<=n;i++)
for(int j=1;j+i-1<=n;j++){
int l=j,r=j+i-1;
f[l][r]=1e8;
for(int k=l;k<r;k++) f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+a[r]-a[l-1]);//这里有点像树的感觉
}
cout<<f[1][n];
return 0;
}
最后
以上就是儒雅薯片为你收集整理的动态规划从入门到提升详解入门解决动态规划的一般思路动态规划之线性DP动态规划之背包问题动态规划之区间DP的全部内容，希望文章能够帮你解决动态规划从入门到提升详解入门解决动态规划的一般思路动态规划之线性DP动态规划之背包问题动态规划之区间DP所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复