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;

}

以上便是这篇文章的所有内容，希望对你有帮助。~~

巴特西

C++ 动态规划:一维动态规划，背包问题，区间动态规划