int

nums[]{3,1,7,9,12,78,32,5,10,11,21,32,45,22}现给定区间信息[…1.

区间类型问题指求一个数列中某一段区间的值包括求和、最值等简单或复杂问题。

此类问题也适用于动态规划思想。

int

nums[]{3,1,7,9,12,78,32,5,10,11,21,32,45,22}现给定区间信息[3,6]求区间内所有数字相加结果。

即求如下图位置数字之和。

Tips

如果对任意区间的求解要求较频繁会存在大量的重复计算。

如分别求区间[2,5]和[1,5]之和时分析可知区间[1,5]结果等于区间[2,5]的结果加上nums[1]的值或者说区间[2,5]的值等于[1,5]的值减nums[1]。

简而言之只需要求出一个如上两个区间中一个区间的值另一个区间的值就可得到。

如上的问题便是简单的区间类型问题解决此类问题的方案称为简单区间类型动态规划。

dp数组也可称为前缀和数组。

编码实现

{3,1,7,9,12,78,32,5,10,11,21,32,45,22};int

dp[100];int

sizesizeof(nums)/sizeof(int);for(int

i0;

dp[i]nums[i];}else{dp[i]dp[i-1]nums[i];}}//输出dp信息for(int

i0;

dp[r]-dp[l-1];如下代码实现输入任意区间信息输出区间和信息。

#include

{3,1,7,9,12,78,32,5,10,11,21,32,45,22};int

dp[100];int

sizesizeof(nums)/sizeof(int);for(int

i0;

{dp[i]dp[i-1]nums[i];}}//输出dp信息for(int

i0;

{cinlr;if(l-1)break;sumdp[r]-dp[l-1];coutsumendl;}return

}前缀和是区间动态规划的极简单应用下文继续讲解几道典型的区间类型问题。

典型案例

设有N(N300)堆石子排成一排其编号为1,2,3...N每堆石子有一定的质量m[i]

(m[i]1000)。

现在要将这N堆石子合并成为一堆每次只能合并相邻的两堆合并的代价为这两堆石子的质量之和合并后与这两堆石子相邻的石子将和新堆相邻。

合并时由于选择的顺序不同合并的总代价也不相同。

试找出一种合理的方法使总的代价最小并输出最小代价。

1,2,3

合并编号为1、2的石子合并代价为3再合并新堆和第3堆石子代价为6。

总代价为9。

合并编号为2、3的石子合并代价为5再合并新堆和第1堆石子代价为6。

总代价为11。

任意相邻两堆石子合并的结果是以这两堆石子的编号作为左、右边界的区间和。

如合并编号1,2的石子代价为区间[1,2]的和

如样例所示两种合并方案的代价分别为3,5取最小值3再加上所有石子的质量和6即为最后答案9。

对于n堆的石子可以随意在中间画出一条分割线把n堆石子抽象成左、右2

但是左堆不是真正意义上只有一堆石子是由许多石子堆组成的一个逻辑整体有其内部的合并方案且不止一种站在宏观的角度不用关心其内部如何变化只需关心多种合并方案的最小值是多少。

同理也只需关心右堆最终返回的最佳值。

最终合并最小值所有石子堆的总质量值左堆最小合并值右堆最小合并值如果原始问题是一个根问题则求解左堆或右堆的最佳合并值就是一个子问题所以合并石子这道题本质是符合递归特点的。

绘制如下图递归树根问题为原始问题区间划分可以从第一堆石子开始然后再移动分割线最后再在多个子问题返回值中取最小值。

Tips

i1;in;i){cinsz[i];}//动态规划计算前缀和for(int

int

sums[r]-s[l-1];//计算可分方案且返回所有分割方案中的最小值for(int

kl;

);}//返回最后一次合并的值加上左、右区间的合并值return

sumres;

sums[r]-s[l-1];//计算可分方案且返回所有分割方案中的最小值for(int

kl;

}递归是由上向下逐步向子问题求助类似问题也可以采用由下向上的动态规划方案实现。

基本思路每一次合并过程先两两合并再三三合并…最后N堆合并。

*动态规划

1]);}ansmax(ans,dp[i][j]);}return

ans;

resdpSz();cout动态规划方案resendl;printf(%d\n,

dp[1][n]);return

颗每次我们可以选择相邻的两堆石子合并代价是两堆石子数目的和现在我们要一直合并这些石子使得最后只剩下一堆石子问总代价最少是多少?

假设石子有

如果考虑环形问题则任何数字都可以为头、为尾则会出现如下几种数列。

动态规划实现