区间类 DP

Stone game

note that, this problem is kind of partition problem. Actually, we need to find the minimum cost when merging the stones from 0 to n - 1.

So it is eary to define the state, dp[i][j] is the minimum cost when merging the stones from ith to jth.

dp[i][j] = min(dp[i][k]+dp[k+1][j]+sum[i,j]) 对于所有k属于{i,j-1}

initialize: for each i, dp[i][i] = 0,

answer: return dp[0][n-1]

public int stoneGame(int[] A) {
    // write your code here
    if (A == null || A.length == 0) return 0;

    int n = A.length;

    // initialize 
    int[][] dp = new int[n][n];
    boolean[][] flag = new boolean[n][n];

    int[][] sum = new int[n][n];
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            sum[i][j] = i == j ? A[j] : sum[i][j - 1] + A[j];
        }
    }

    return memorySearch(0, n-1, dp, flag, sum);
}

private int memorySearch(int left, int right, int[][] dp, boolean[][] flag, int[][] sum) {
    if (flag[left][right] == true) return dp[left][right];

    flag[left][right] = true;

    if (left == right) return dp[left][right];   // for the single element, the merging cost is 0
    dp[left][right] = Integer.MAX_VALUE;
    for (int k = left; k < right; ++k) {
        dp[left][right] = Math.min(dp[left][right], 
                memorySearch(left, k, dp, flag, sum) +
                memorySearch(k + 1, right, dp, flag, sum) + sum[left][right]);

    }
    return dp[left][right];
}

time complexity is O(n^2)

why ?

算法复杂度
对于多项式算法复杂度，比如：2×N^3 + 3 × N^2, 我们只计算最高此项，且忽略系数(常数)， 记做O(N^3)。
这道题目的第一种解法：记忆化解法。其本质上是一种分治的方法。
对于分治方法，我们关注两个部分，分解的子问题数量和合并子问题的复杂度。
（完整严谨的分治算法复杂度的计算比较麻烦，有兴趣您可以研究一下，这里我们要快速的分析出分治的复杂度。）

对于每个长度是m的区间，其会分解出来m个子问题。m的范围是1～N，所以总的复杂度就是1+2+3+···+N， 也就是O(N^2)。

我们也可以从另外的角度来思考，分治的过程就是暴力的枚举所有的连续区间，而这些区间一共也就是1+2+3+···+N，N^2个。

两个子问题的合并，在本题中就是一个数值比较运算， 因此是O(1), 所以整体复杂度是O(N^2).
(其实在预处理的时候，两重循环就已经是O(N^2)了。所以整体复杂度不会低于O(N^2), 并且由于递归，实际复杂度的常数会略大)

第二种方法其本质依然是分治。
同样在预处理阶段就达到了O(N^2)。并且后续的递归过程同上一个一样，只是写法上略有不同而已。
体现在不使用visit[]数组标记，而是利用Dp初始化值的方式做记忆化标记。

区间动态规划的三种实现方式： （先计算小区间，再计算大区间）

• 先循环区间长度，再循环起点位置

• 起点倒过来循环，终点正过去循环

• 记忆化搜索

Burst Balloons

note that, we need to think more. (DFS + DP)

helper() means we have burst the balloons and return the maximum value, so the helper(array, start, end, cache) means that in the interval from start to end, we have burst all the balloons in the interval from start to end. But how to burst them? we just keep the balloon i, and burst all the balloon both in the interval [start, i - 1], and interval [i + 1, end].

public class Solution {   
    public int maxCoins(int[] nums) {
        int[] array = new int[nums.length + 2];
        for(int i = 0; i < array.length; i ++){
            if(i == 0 || i == array.length - 1){
                array[i] = 1;
                continue;
            }
            array[i] = nums[i - 1];
        }
        int[][] cache = new int[array.length][array.length];
        return helper(array, 1, array.length - 2, cache);
    }

    private int helper(int[] array, int start, int end, int[][] cache){
        if(start > end){
            return 0;
        }
        if(cache[start][end] > 0){
            return cache[start][end];
        }
        for(int last = start; last <= end; last ++){
            int left = helper(array, start, last - 1, cache);
            int right = helper(array, last + 1, end, cache);
            cache[start][end] = Math.max(cache[start][end], left + right + array[start - 1] * array[last] * array[end + 1]);
        }
        return cache[start][end];
    }
}

another method to address the problem is to use for loop, (??????????????????)

dp[i][j] 代表 burst i+1 ~ j-1 这段时间的所有气球之后，只剩下 i,j 的最大收益。

将原来的数组前面和后面增加两个1，最后结果就是 dp[0][n - 1]（burst 掉所有气球只剩两个1）

将原数组两端加上1
• [4,3,5] => [1,4,3,5,1]
•数组长度n从3变为5

• State:
• dp[i][j]表示把第i+1到第j-1个气球打爆，剩下i,j的最大收益

• Function:
•对于所有k属于{i + 1,j - 1},表示第k号气球最后打爆。

• score = arr[i] * arr[k] * arr[j]

• dp[i][j] = max(dp[i][k]+dp[k][j]+score)

  • Intialization:• dp[i][i] = 0

  • Answer:
  • dp[0][n-1]

public class Solution {
    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0){
            return 0;
        }

        nums = init(nums);
        int[][] dp = new int[nums.length][nums.length];

        for (int i = nums.length - 1; i >= 0; i--) {
            for (int j = i + 2; j < nums.length; j++) {
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][k] +  dp[k][j] + nums[i] * nums[k] * nums[j]);
                }
            }
        }

        return dp[0][nums.length - 1];
    }

    public int[] init(int[] nums){
        int[] temp = new int[nums.length + 2];
        temp[0] = 1;
        for(int i = 1; i < temp.length - 1; i++){
            temp[i] = nums[i - 1];
        }
        temp[temp.length - 1] = 1;
        return temp;
    }
}