区间型
详解
Stone Game
There is a stone game.At the beginning of the game the player picksnpiles of stones in a line.
The goal is to merge the stones in one pile observing the following rules:
- At each step of the game,the player can merge two adjacent piles to a new pile.
- The score is the number of stones in the new pile.
You are to determine the minimum of the total score.
思路：
典型的区间型问题，需要借助 prefix sum来计算i到j的merge cost。dp定义也是很典型的从i到j的合并最少cost。
代码实现就是三层for 循环。 第一层是length，这是subproblem的规模，我们需要从小到大来计算。第二层是起始位置，第三层是终点位置。
public int stoneGame(int[] A) {
// Write your code here
if (A == null || A.length == 0)
return 0;
int n = A.length;
int[] sum = new int[n+1];
for (int i = 1; i <= n; i++) {
sum[i] = sum[i-1] + A[i-1];
}
int[][] dp = new int[n+1][n+1];
for (int i = 1; i <= n; i++) {
dp[i][i] = 0;
}
for (int i = 2; i <= n; i++) { //length
for (int j = 1; j+i-1 <= n; j++) { //start
int k = j + i -1;
dp[j][k] = Integer.MAX_VALUE;
for (int l = j; l < k; l++) {
dp[j][k] = Math.min(dp[j][k], dp[j][l] + dp[l+1][k] + sum[k] - sum[j-1]);
}
}
}
return dp[1][n];
}
Stone Game II
将上一道题延伸成环。因此需要double length for dp。最后需要遍历一遍得到最小值。
public int stoneGame2(int[] A) {
// Write your code here
if (A == null || A.length == 0)
return 0;
int n = A.length;
// cal sum to get sum from i to j by sum[j] - sum[i-1]
int[] sum = new int[2*n+1];
for (int i = 1; i <= 2 * n; i++) {
sum[i] = sum[i-1] + A[(i-1) % n];
}
// initialization cost to merge self is 0
int[][] dp = new int[2*n + 1][2 * n + 1];
for (int i = 1; i <= 2*n; i++) {
dp[i][i] = 0;
}
for (int i = 2; i <= n; i++) { // length (calced when length == 1)
for (int j = 1; j + i -1 <= 2 *n; j++) {// start point
int k = j+ i - 1; // end point
dp[j][k] = Integer.MAX_VALUE;
// loop over from start to end
for (int l = j; l < k; l++) {
dp[j][k] = Math.min(dp[j][k], dp[j][l] + dp[l+1][k] + sum[k] - sum[j-1]);
}
}
}
int ans = Integer.MAX_VALUE;
// loop over dp result
for (int i = 1; i <= n; ++i)
if (dp[i][i + n - 1 ] < ans)
ans = dp[i][i + n - 1];
return ans;
}
Burst Balloons
Givennballoons, indexed from0ton-1. Each balloon is painted with a number on it represented by arraynums. You are asked to burst all the balloons. If the you burst ballooniyou will getnums[left] * nums[i] * nums[right]coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.
Find themaximumcoins you can collect by bursting the balloons wisely.
- You may imagine
nums[-1] = nums[n] = 1. They are not real therefore you can not burst them. - 0 ≤
n≤ 500, 0 ≤nums[i]≤ 100
思路：
这题和stones非常相似，唯一需要注意的是需要在数组两端加上虚拟的1用来计算第一个元素和最后一个元素。
public int maxCoins(int[] nums) {
// Write your code here
if (nums == null || nums.length == 0)
return 0;
int[] A = new int[nums.length+2];
A[0] = 1;
A[A.length-1] = 1;
for (int i = 0; i < nums.length; i++) {
A[i+1] = nums[i];
}
int n = A.length;
int[][] dp = new int[n][n];
for (int i = 1; i <= n-2; i++) {
dp[i][i] = A[i-1] * A[i] * A[i+1];
}
for (int len = 2; len <= n-2; ++len) {
for (int left = 1; left + len - 1 <= n-2; ++left) {
int right = left + len - 1;
for (int k = left; k <= right; ++k) {
dp[left][right] = Math.max(dp[left][right], A[left - 1] * A[k] * A[right + 1] + dp[left][k - 1] + dp[k + 1][right]);
}
}
}
return dp[1][n-2];
}