。

最开始的时候#xff0c;有n堆石子排成一列#xff0c;目标是要将所有的石子合并成一堆。

合并规则如下#xff1a;每一次可以合并相邻位置的两堆石子

每次…题目lintcode476

https://www.lintcode.com/problem/476/description

有一个石子归并的游戏。

最开始的时候有n堆石子排成一列目标是要将所有的石子合并成一堆。

合并规则如下每一次可以合并相邻位置的两堆石子

1:输入:

https://www.lintcode.com/problem/593

堆石头并围成一个

圈即第一堆石头与最后一堆石头相邻。

目标是按照下面的规则将石头合并成一堆在游戏中的每一步玩家可以合并两堆相邻的石头为新的一堆石头。

分数就是新的石头堆的石头个数。

你需要找到最小的总分。

样例

例1输入

从最小长度的i~j开始做dp因为长的i~j肯定能从比他小的段计算出来

算法区间DP

这是一道区间DP问题我们需要用区间表示状态来递推。

设s是表示石头重量的数组设f[i][j]是将s[i,…,j]的石头合并成一个所需的最少能量那么这个最少能量按照最后一步合并的分界线可以分为以下几种情况

1、最后一步是s[i]和s[i1,…,j]合并此时需要的最少能量是f[i1][j]sum(s[i]…s[j]),第一项是合并后者需要的能量第二项是最后一次合并所需要的能量。

s[i]自己只有一个石头不需要合并

2、最后一步是s[i,i1]和s[i2,…,j]合并此时需要的最少能量是f[i][i1]f[i2][j]sum(s[i]…s[j])第一项是合并前两个石头需要的能量第二项是合并后半区间石头需要的能量最后一项是最后一次合并需要的能量

从上面我们可以看出一个规律f[i][j]应该是所有区间分法中前一半区间的石头合并需要的总能量加上后半区间的总能量再加上最后一次合并需要的能量

区间长度从2开始枚举

区间型动态规划线变成环一般的两种方法求补集或者枚举接口处类似House

Robber

476的答案只不过数组长度n扩充为原来的2倍也就是2*n求解过程中动态规划最外层循环i%n0时候记录最小值最小值就是答案

题目lintcode

{//从最小长度的i~j开始做dp因为长的i~j肯定能从比他小的段计算出来if(a

null

Math.min(dp[i][j],dp[i][k]dp[k1][j]sum[j]-sum[i-1]);}}}return

dp[1][n];}

{/*1.算法区间型动态规划线变成环一般的两种方法求补集或者枚举接口处类似House

Robber

这里都不适用。

采用第三种方法将数组变成2倍取长度为n的最小值2.代码实现注意k的下标迷之tle了3.时空复杂度分析时间复杂度

O(n^2)空间复杂度

stoneGame(arr1);}//下面的代码和lintcode

476题代码差不多不同的是本地数组长度变为原来的2倍//因此在新数组求解过动态规划程中需要lenn/2的时候得到最小值就是答案public

static

{//从最小长度的i~j开始做dp因为长的i~j肯定能从比他小的段计算出来if(a

null

Math.min(dp[i][j],dp[i][k]dp[k1][j]sum[j]-sum[i-1]);if(len

n/2){minMath.min(min,dp[i][j]);//.out.println(index:--

len);}}}}return