宁波做网站哪家好,市场监督管理局是工商局吗,重庆口碑最好的装修公司,企业系统查询题目lintcode476 链接#xff0c;描述
https://www.lintcode.com/problem/476/description
有一个石子归并的游戏。最开始的时候#xff0c;有n堆石子排成一列#xff0c;目标是要将所有的石子合并成一堆。合并规则如下#xff1a;每一次可以合并相邻位置的两堆石子
每次…题目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[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]应该是所有区间分法中前一半区间的石头合并需要的总能量加上后半区间的总能量再加上最后一次合并需要的能量
求得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%n0时候记录最小值最小值就是答案
题目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.length0) return 0;int n a.length;int[][] dp new int[n1][n1];int[] sum new int[n1];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; ilen-1 n ; i) {int j ilen-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[k1][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(anull || a.length2) 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倍//因此在新数组求解过动态规划程中需要lenn/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[n1][n1];int[] sum new int[n1];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; ilen-1 n ; i) {int j ilen-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[k1][j]sum[j]-sum[i-1]);if(len n/2){minMath.min(min,dp[i][j]);//.out.println(index:-- len);}}}}return min;}
}
