区间类DP总结

区间类DP的做法，是用memorized search，把大区间拆分为小区间来解。而dp[i][j] 则直观的表示为区别 i 到 j 的最优解。

主要总结一下三道题。

Coin in a line III
http://www.lintcode.com/en/problem/coins-in-a-line-iii/

这道题正向去解：
dp[i][j] 表示 i 到 j 的区间中，先手取可以获得的最大值。由于先手取完，后手也可以有两种情况，因而通项公式是：
dp[i][j] = max(nums[i] + min(dp[i+2][j], dp[i+1][j-1]), nums[j] + min(dp[i+1][j-1], dp[i][j-2]))

bool firstWillWin(vector<int> &values) {
        // write your code here
        if(values.empty()) return true;
        int sum = 0, n = values.size();
        for(int i=0; i<n; i++){
            sum += values[i];
        }
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        vector<vector<int>> record(n, vector<int>(n, 0));
        int ret = search_util(values, 0, n-1, visited, record);
        return ret >= sum - ret;
    }
    
    int search_util(vector<int> &values, int left, int right, vector<vector<bool>> &visited, vector<vector<int>> &record){
        if(left > right) return 0;
        else if(left == right) return values[left];

        if(visited[left][right]){
            return record[left][right];
        }
        int left_value = values[left] + min(search_util(values, left+1, right-1, visited, record), search_util(values, left+2, right, visited, record));
        int right_value = values[right] + min(search_util(values, left+1, right-1, visited, record), search_util(values, left, right-2, visited, record));
        int cur = max(left_value, right_value);
       
        record[left][right] = cur;
        visited[left][right] = true;
        return cur;
    }

值得注意的是，这道coins in the line III 有一个hacky的follow up：如果数组是even个数，如何快速判断先手能否获胜。这里只要判断 奇数和是否等于偶数和就可以了。由于先手可以选择take all evens or all odds，只要不等于就必赢。等于就可以是tie，所以赢不了。

Stone Game:
http://www.lintcode.com/en/problem/stone-game/#

dp[i][j] 表示为 i 到 j 的区间中，把所有石子合并的最小花费。在 i - j 的区间中，对于其中一点k，以 k 为最后合并的那个点，的score为 dp[i][k] + dp[k+1][j] + sum{i -> j}。所以对所有区间中的点取最小值。
通项公式为：

dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum{i -> j}); // loop k from i to j

class Solution {
public:
    /**
     * @param A an integer array
     * @return an integer
     */
    int search_util(vector<int>& A, vector<vector<bool>> &visited, vector<vector<int>> &record, int left, int right){
        if(left >= right) return 0;
        else if(visited[left][right]) return record[left][right];
        int res = INT_MAX;
        for(int i=left; i<right; i++){
            res = min(res, search_util(A, visited, record, left, i) + search_util(A, visited, record, i+1, right));
        }
        res += presum[right] - presum[left-1];
        visited[left][right] = true;
        record[left][right] = res;
        return res;
    } 
    
    int stoneGame(vector<int>& A) {
        // Write your code here
        if(A.empty()) return 0;
        presum[-1] = 0;
        int size = A.size();
        for(int i=0; i<size; i++){
            presum[i] = A[i] + presum[i-1];
        }
        vector<vector<bool>> visited(size, vector<bool>(size, false));
        vector<vector<int>> record(size, vector<int>(size, 0));
        int ret = search_util(A, visited, record, 0, size-1);
        return ret;
    }
private:
    unordered_map<int, int> presum;
};

Burst Balloons:
http://www.lintcode.com/en/problem/burst-balloons/#

dp[i][j]表示 i 到 j 区间中，打爆所有气球的最大coin数目。而针对区间中一点 k，以k 为最后一点打爆，的coin数目 为
dp[i][k-1] + dp[k+1][k] + nums[i] * nums[left-1] * nums[right+1];

所以通项公式为：

dp[i][j] = min(dp[i][k-1] + dp[k+1][k] + nums[i] * nums[left-1] * nums[right+1]); // loop k from i to j

int maxCoins(vector<int>& nums) {
        // Write your code here
        if(nums.empty()) return 0;
        else if(nums.size() == 1) return nums[0];
        nums.insert(nums.begin(), 1); nums.push_back(1);
        int n = nums.size();
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        vector<vector<int>> record(n, vector<int>(n, 0));
        int max_ret = search_util(nums, 1, n-2, visited, record);
        return max_ret;
    }
    
    int search_util(vector<int>& nums, vector<vector<bool>> &visited, vector<vector<int>> &record, int left, int right){
        if(left > right) return 0;
        else if(visited[left][right]) return record[left][right];
        int res = INT_MIN;
        for(int i=left; i<=right; i++){
            int cur = search_util(nums, visited, record, left, i-1) + search_util(nums, visited, record, i+1, right);
            res = max(res, cur + nums[i] * nums[left-1] * nums[right+1]);
        }
        visited[left][right] = true;
        record[left][right] = res;
        return res;
    }