c++动态规划详解

动态规划的定义

---

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。动态规划是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。简单来说动态规划其实就是，给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后呢，把子问题答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法。

动态规划的基本思想

---

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。

一维动态规划

---

示例：

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

要想跳到第 10 级台阶，要么是先跳到第 9 级，然后再跳 1 级台阶上去;要么是先
跳到第 8 级，然后一次迈 2 级台阶上去。同理，要想跳到第 9 级台阶，要么是先跳到第 8 级，然后再跳 1 级台阶上去;要么是先跳到第 7 级，然后一次迈 2 级台阶上去。要想跳到第 8 级台阶，要么是先跳到第 7 级，然后再跳 1 级台阶上去;要么是先跳到第 6 级，然后一次迈 2 级台阶上去。
假设跳到第 n 级台阶的跳数我们定义为 f(n)，很显然就可以得出以下公式：
F(10) = f(9)+f(8)
f (9) = f(8) + f(7)
f (8) = f(7) + f(6)
...
f(3) = f(2) + f(1)
即通用公式为: f(n) = f(n-1) + f(n-2)
那 f(2) 或者 f(1) 等于多少呢？
当只有 2 级台阶时，有两种跳法，第一种是直接跳两级，第二种是先跳一级，然后再跳一
级。即 f(2) = 2;当只有 1 级台阶时，只有一种跳法，即 f（1）= 1；

这样就可以用递归算法解决因此，青蛙跳阶，递归解法的时间复杂度 = O(1) * O(2^n) = O(2^n)，就是指数级别的，爆炸增长的，如果 n 比较大的话，超时很正常的了。
回过头来，你仔细观察这颗递归树，你会发现存在大量重复计算，比如 f（8）被计算
了两次，f（7）被重复计算了 3 次...所以这个递归算法低效的原因，就是存在大量的重复
计算！

既然存在大量重复计算，那么我们可以先把计算好的答案存下来，即造一个备忘录，等到下次需要的话，先去备忘录查一下，如果有，就直接取就好了，备忘录没有才开始计算，那就可以省去重新重复计算的耗时啦！这就是带备忘录的解法。

使用动态规划解法如下：

///关键代码：
int dp[10005];
dp[1]=1;
dp[2]=2;
int numWays(int n) {
for (int i = 3; i <= n; i++) {
dp[i] = (dp[i-1] + dp[i-2]);   //状态转移方程
}
return dp[n];
}

f(n-1)和 f(n-2) 称为 f(n) 的最优子结构
f(n)= f(n-1)+f(n-2) 就称为状态转移方程
f(1) = 1, f(2) = 2 是边界
比如 f(10)= f(9)+f(8),f(9) = f(8) + f(7) ,f(8)就是重叠子问题

动态规划的解题思路如下：
1.穷举分析
2.确定边界
3.找出规律，确定最优子结构
4.写出状态转移方程

 

背包类型动态规划

---

背包问题的定义：

背包问题(Knapsack problem)是一种组合优化的 NP 完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过 W 的前提下，总价值是否能达到 V？它是在 1978 年由 Merkle 和 Hellman 提出的，定义如下：我们有 n 种物品，物品 j 的重量为 wj，价格为 pj。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为 W。如果限定每种物品只能选择 0 个或 1 个，则问题称为 0-1 背包问题。

背包问题的原理：

动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。

背包问题的分类

背包问题可以总结为三类：01 背包问题、完全背包问题以及分组背包问题。
01 背包问题：每个元素最多取 1 次。具体来讲：一共有 N 件物品，第 i（i 从 1 开
始）件物品的重量为 w[i]，价值为 v[i]。在总重量不超过背包承载上限 W 的情况下，能
够装入背包的最大价值是多少？
完全背包问题：每个元素可以取多次。具体来讲：完全背包与 01 背包不同就是每种
物品可以有无限多个：一共有 N 种物品，每种物品有无限多个，第 i（i 从 1 开始）种
物品的重量为 w[i]，价值为 v[i]。在总重量不超过背包承载上限 W 的情况下，能够装入
背包的最大价值是多少？
分组背包问题：有多个背包，需要对每个背包放入物品，每个背包的处理情况与完全
背包完全相同。
在完全背包问题当中根据是否需要考虑排列组合问题（是否考虑物品顺序），可分为
两种情况，我们可以通过内外循环的调换来处理排列组合问题，如果题目不是排列组合问
题，则这两种方法都可以使用（推荐使用组合来解决）
而每个背包问题要求的也是不同的，按照所求问题分类，又可以分为以下几种：
1、最值问题：要求最大值/最小值
2、存在问题：是否存在…………，满足…………
3、组合问题：求所有满足……的排列组合

解题模板：

1.01 背包问题

【题目描述】
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
【输入格式】
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
【输出格式】
输出一个整数，表示最大价值。
【思路解析】
「01 背包」是指给定物品价值与体积（对应了「给定价值与成本」），在规定容量下
（对应了「限定决策规则」）如何使得所选物品的总价值最大。
1．01 背包是动态规划类问题。一般需要将主问题分解为多个子问题，然后记录下不
同子问题的解，最终才能推得最终问题的答案。
2．定义子问题：前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值是多少？
3．我们用 f[i][v] 表示 前 i 件物 恰放入一个 容量为 v 的背包可以获得的 最大价值。
4．要求主问题 f[i][v] 就得先知道子问题 F[i-1][v]和 f[i-1][ v-v[i] ]是多少 。然后通过状
态转移方程：f[i][v]=max{ f[i-1][v] , f[i-1][ v-v[i] ]+c[i]] }
5．状态转移方程是整个背包问题的核心。解释：“前 i 个物品放入容量为 v 的背包中”
可以转化为“前 i-1 个物品已经放入了容量为 v 的背包中（即为 f[i-1][v]）” 和 “第 i 个物品
放还是不放入背包中？”
 如果第 i 个物品不放入背包，那么 f[i][v]=f[i-1][v]
 如果第 i 个物品放入背包，那么 f[i][v]=f[i-1][ v-v[i] ] + c[i]，此时这个式子里面只有
f[i-1][ v-v[i] ]未知，问题转化为“前 i-1 个物品放入了剩余容量为 v-v[i]的背包中能获
得最大价值是多少？
代码实现：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxN=1010;
int f[maxN][maxN];                  //f[i][j]体积为 j 的背包在前 i 件物品中能装的最大价值
int v[maxN];                        //物品体积
int w[maxN];                        //物品价值
int main()
{
int n,m;
memset(f,0,sizeof(f));
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d %d",&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];                          //体积为 i-1 可以拿 f[i-1][j], 那体积比它大的 i 的至少也可以拿它那么多吧
if(j >= v[i])                               // 防止 f[j-v[i]]越界
f[i][j] = max(f[i-1][j] , f[i-1][j - v[i]] + w[i]);
}
}
printf("%d\n",f[n][m]);
return 0;
}

2.完全背包

【题目描述】
有 n 种物品和一个容量为 c 的背包，每种物品都有无限件。
第 i 件物品的体积是 v[i]，价值是 w[i]。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
【输入样例】
2 5
1 1
2 2
【输出样例】
5
解释：选一件物品 1，再选两件物品 2，可使价值最大 。
【思路解析】
我们可以直接将 01 背包的「状态定义」拿过来用：
dp[i][j]代表考虑前 i 件物品，放入一个容量为 j 的背包可以获得的最大价值。
由于每件物品可以被选择多次，因此对于某个 dp[i][j] 而言，其值应该为以下所有可
能方案中的最大值：
选择 0 件物品 i 的最大价值，即 dp[i-1][j]
选择 1 件物品 i 的最大价值，即 dp[i-1][j-v[i]]+w[i]
选择 2 件物品 i 的最大价值，即 dp[i-1][j-2v[i]]+2w[i]
...
选择 k 件物品 i 的最大价值，dp[i-1][j-kv[i]]+kw[i]
由此我们可以得出「状态转移方程」为：
dp[i][j] = max(dp[i-1][j],dp[i-1][j-2v[i]]+2w[i]), 0<k*v[i]≤j
代码实现

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxN=1010;
int f[maxN][maxN];   //f[i][j]体积为 j 的背包在前 i 件物品中能装的最大价值
int v[maxN];         //物品体积
int w[maxN];        //物品价值
int main()
{
int n,c;
memset(f,0,sizeof(f));
scanf("%d %d",&n,&c);
for(int i=0;i<n;i++){
scanf("%d %d",&v[i],&w[i]);        //各物品价值
}
// 先预处理第一件物品
for (int j = 0; j <= c; j++) {
                                  // 显然当只有一件物品的时候，在容量允许的情况下，能选多少件就选多少件
int maxK = j / v[0];
f[0][j] = maxK * w[0];
}
for (int i = 1; i < n; i++) {
for (int j = 0; j <= c; j++) {
               // 不考虑第 i 件物品的情况（选择 0 件物品 i）
int x = f[i - 1][j];
              // 考虑第 i 件物品的情况
int y = 0;
int k=1;           //选择第 i 件物品的数量
while(j >= v[i] * k){
y = max(y, f[i - 1][j - k * v[i]] + k * w[i]);
k++;
}
f[i][j] = max(x, y);
}
}
printf("%d\n",f[n-1][c]);
return 0;
}

区间动态规划

区间动态规划定义：

区间类动态规划是线性动态规划的拓展，它在分阶段划分问题时，与阶段中元素出现
的顺序和由前一阶段的哪些元素合并而来有很大的关系。如状态 f[i][j]，它表示以已合并的
次数为阶段、以区间的左端点 i 为状态，它的值取决于第 i 个元素和第 j 个元素断开的位置
k，即 f[i][k]+f[k+1][j]的值。这一类型的动态规划，阶段特征非常明显，求最优值时需要预
先设置阶段内的区间统计值，还要以动态规划的起始位置来判断。
区间类动态规划的特点：
合并：即将两个或多个部分进行整合，当然也可以反过来，也就是对一个问题分解成
两个或多个部分。
特征：对将问题分解成为两两合并的形式。
求解：对整个问题设最优值、枚举合并点，将问题分解成左右两个部分，最后合并左
右两个部分的最优值得到原问题的最优值。有点类似分治算法的解题思想。
区间类动态规划的典型应用有：石子合并、能量项链、凸多边形的划分等。
区间型 DP 中的区间通常指的就是字面意义上的区间，以一组数列为例，那么[i][j]表示
的就是 i 到 j 的这个区间。
区间型动态规划的递归关系，通常是呈现出去头去尾的特点，以下面的伪代码为例。
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) //区间[i][j]由去掉头(或者去掉尾)的[i + 1][j](dp[i][j - 1])推
出
基于此种特性，区间型 DP 的代码实现通常要对区间长度进行循环，即从区间长度短
的循环到区间长度长的，当求当前状态的值的时由于使用到的子状态的区间长度都小于当
前状态，因此都可以推出，非常的合理且符合直觉。

伪代码：

for (int i = 1; i <= len; i++)               //循环区间长度
for (int j = 0; j <= n - len; j++)            //循环做端点
for (int z = j + 1; z < n; z++)              //循环右端点
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);          //转移方程

例题解析：石子合并
【题目描述】
将 n 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。规定每次只能选相邻的
两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。
请编写一个程序，读入堆数 n 及每堆的石子数，并进行如下计算：
选择一种合并石子的方案，使得做 n-1 次合并得分总和最大。
选择一种合并石子的方案，使得做 n−1 次合并得分总和最小。
【输入格式】
输入第一行一个整数 n，表示有 n 堆石子。
第二行 n 个整数，表示每堆石子的数量。
【输出格式】
输出共两行：
第一行为合并得分总和最小值，
第二行为合并得分总和最大值。
【输入样例】
4
4 5 9 4
【输出样例】
43
54
数据范围与提示
对于 100%的数据，有 1≤n≤200。
【思路解析】
最初的第 l 堆石子和第 r 堆石子被合并成一堆，则说明 l~r 之间的每堆石子也已经被
合并，这样 l 和 r 才有可能相邻。因此，在任意时刻，任意一堆石子均可以用一个闭区间
[l，r]来描述，表示这堆石子是由最初的第 l~r 堆石子合并而成的，其重量为∑ai(l≤i≤r)。
另外，一定存在一个整数 k(l≤k<r)，在这堆石子形成之前，先有第 l~k 堆石子(闭区间[l，k])
被合并成一堆，第 k+1~r 堆石子(闭区间[k+1，r])被合并成一堆，然后这两堆石子才合并成
[l，r]。
对应到动态规划中，就意味着两个长度较小的区间上的信息向一个更长的区间发生了
转移，划分点 k 就是转移的决策。自然地，应该把区间长度 len 作为 DP 的阶段。不过，区
间长度可以由左端点和右端点表示，即 len=r-l+1。本着动态规划“选择最小的能覆盖状态
空间的维度集合”的思想，我们可以只用左、右端点表示 DP 的状态。
设 sum[i]表示从第 l 堆到第 i 堆石子数总和 sum[i]=a[1]+a[2]…+a[i]。
Fmax[i][j]表示从第 i 堆石子合并到第 j 堆石子的最大的得分。
Fmin[i][j]表示从第 i 堆石子合并到第 j 堆石子的最小的得分。
则状态转移方程为：
Fmax[i][j]=max{Fmax[i][k]+Fmax[k+1][j]+sum[j]-sum[i-1]}(i≤k≤j-1).
Fmin[i][j]=min(Fmin[i][k]+Fmin[k+1][j]+sum[j]-sum[i-1])(i≤k≤j-1)
初始条件：Fmax[i][i]=0，Fmin[i][i]=INF。
时间复杂度为 O(n³)。
代码实现

#include <iostream>
using namespace std;
const int maxn=205,inf=0x7fffffff/2;
int f1[maxn][maxn],f2[maxn][maxn],s[maxn][maxn]={0};
int a[maxn],sum[maxn]={0},n,ans1,ans2;
void dp(){
for(int l=2;l<=n;l++){
for(int i=1;i<=2*n-l+1;i++){
int j=i+l-1;
f1[i][j]=inf;
f2[i][j]=0;
for(int k=i;k<j;k++){
f1[i][j]=min(f1[i][j],f1[i][k]+f1[k+1][j]);
f2[i][j]=max(f2[i][j],f2[i][k]+f2[k+1][j]);
}
f1[i][j]+=sum[j]-sum[i-1];
f2[i][j]+=sum[j]-sum[i-1];
}
 
}
ans1=inf,ans2=0;
for(int i=1;i<=n;i++)
ans1=min(ans1,f1[i][i+n-1]);
for(int i=1;i<=n;i++)
ans2=max(ans2,f2[i][i+n-1]);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i+n]=a[i];
}
for(int i=1;i<=n*2;i++){
sum[i]=sum[i-1]+a[i];
f2[i][i]=0;
f1[i][i]=0;
}
dp();
printf("%d\n%d\n",ans1,ans2);
return 0;
}