区间型动态规划典型题目：lintcode 476 · 石子归并【中等，免费】lintcode 593 · 石头游戏 II【中等 vip】

题目lintcode476 链接，描述

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

有一个石子归并的游戏。最开始的时候，有n堆石子排成一列，目标是要将所有的石子合并成一堆。合并规则如下：每一次可以合并相邻位置的两堆石子
每次合并的代价为所合并的两堆石子的重量之和
求出最小的合并代价。样例
样例 1:输入: [3, 4, 3]
输出: 17
样例 2:输入: [4, 1, 1, 4]
输出: 18
解释: 1. 合并第二堆和第三堆 => [4, 2, 4], score = 22. 合并前两堆 => [6, 4]，score = 83. 合并剩余的两堆 => [10], score = 18

题目lintcode593 链接，描述

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

有一个石头游戏。在游戏的开始的时候，玩家挑选了 n 堆石头并围成一个 圈，即第一堆石头与最后一堆石头相邻。目标是按照下面的规则将石头合并成一堆：在游戏中的每一步，玩家可以合并两堆相邻的石头为新的一堆石头。分数就是新的石头堆的石头个数。你需要找到最小的总分。样例
例1：输入：
[1,1,4,4]
输出：18
解释：
1.合并前两个=> [2,4,4]，得分+2
2.合并前两个=> [6,4]，得分+6
3.合并最后两个=> [10]，得分+10
例2：输入：
[1,1,1,1]
输出：8
解释：
1.合并前两个=> [2,1,1]，得分+2
2.合并后两个=> [2,2]，得分+2
3.合并最后两个=> [4]，得分+4

思路

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

算法：区间DP

这是一道区间DP问题，我们需要用区间表示状态来递推。设s是表示石头重量的数组，设f[i][j]是将s[i,…,j]的石头合并成一个所需的最少能量，那么这个最少能量按照最后一步合并的分界线可以分为以下几种情况：

1、最后一步是s[i]和s[i+1,…,j]合并，此时需要的最少能量是f[i+1][j]+sum(s[i]…s[j]),第一项是合并后者需要的能量，第二项是最后一次合并所需要的能量。s[i]自己只有一个石头，不需要合并

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

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

求得A的前缀和
区间长度从2开始枚举，
根据上诉思路可得递推式
dp[l][r] =min(dp[l][r], dp[l][j] + dp[j + 1][r] + sum_a[r + 1] - sum_a[l])
记得初始化dp[l][r]为一个较大值
结果存在dp[0][size-1]中
复杂度分析

时间复杂度O(n^3)
区间dp的复杂度
空间复杂度O(n^2)
dp数组的大小

lintcode 593 :
1.算法
区间型动态规划，线变成环，一般的两种方法，求补集，或者枚举接口处，类似House Robber
II. 这里都不适用。 采用第三种方法：将数组变成2倍，取长度为n的最小值
2.代码实现注意
可以直接lintcode 476的答案，只不过数组长度n扩充为原来的2倍也就是2*n，求解过程中，动态规划最外层循环i%n==0时候，记录最小值，最小值就是答案

题目lintcode 476答案

public class Solution {/*** @param a: An integer array* @return: An integer*/public int stoneGame(int[] a) {//从最小长度的i~j开始做dp，因为长的i~j肯定能从比他小的段计算出来if(a ==null || a.length==0) return 0;int n= a.length;int[][] dp = new int[n+1][n+1];int[] sum = new int[n+1];for (int i = 1; i <=n ; i++) {sum[i] = sum[i-1]+a[i-1];}for (int len = 2; len <=n ; len++) {for (int i = 1; i+len-1 <=n ; i++) {int j= i+len-1;dp[i][j] = Integer.MAX_VALUE;for (int k = i; k <j ; k++) {dp[i][j] = Math.min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);}}}return dp[1][n];}
}

题目 lintcode 593 答案

public class Solution {/*** @param a: An integer array* @return: An integer*/public int stoneGame2(int[] a) {/*1.算法区间型动态规划，线变成环，一般的两种方法，求补集，或者枚举接口处，类似House Robber II. 这里都不适用。采用第三种方法：将数组变成2倍，取长度为n的最小值2.代码实现注意k的下标迷之tle了3.时空复杂度分析时间复杂度 : O(n^2)空间复杂度 : O(n^2)*/if(a==null || a.length<2) return 0;int n = a.length;int[] arr1 = new int[n*2];for (int i = 0; i <2*n ; i++) {arr1[i]= a[i%n];}return stoneGame(arr1);}//下面的代码和lintcode 476题代码差不多，不同的是：本地数组长度变为原来的2倍//因此在新数组求解过动态规划程中，需要len==n/2的时候，得到最小值，就是答案public static int stoneGame(int[] a) {//从最小长度的i~j开始做dp，因为长的i~j肯定能从比他小的段计算出来if(a== null || a.length ==0)return 0;int n = a.length;int[][] dp = new int[n+1][n+1];int[] sum = new int[n+1];for (int i = 1; i <=n ; i++) {sum[i] =sum[i-1]+a[i-1];}int min = Integer.MAX_VALUE;for (int len = 2; len <=n ; len++) {for (int i = 1; i+len-1 <=n ; i++) {int j = i+len-1;dp[i][j] = Integer.MAX_VALUE;for (int k = i; k <j ; k++) {dp[i][j] = Math.min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);if(len == n/2){min=Math.min(min,dp[i][j]);//.out.println("index:--  "+len);}}}}return min;}
}