區(qū)間類DP的做法，是用memorized search，把大區(qū)間拆分為小區(qū)間來(lái)解。而dp[i][j] 則直觀的表示為區(qū)別 i 到 j 的最優(yōu)解。

主要總結(jié)一下三道題。

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

這道題正向去解：
dp[i][j] 表示 i 到 j 的區(qū)間中，先手取可以獲得的最大值。由于先手取完，后手也可以有兩種情況，因而通項(xiàng)公式是：
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 有一個(gè)hacky的follow up：如果數(shù)組是even個(gè)數(shù)，如何快速判斷先手能否獲勝。這里只要判斷 奇數(shù)和是否等于偶數(shù)和就可以了。由于先手可以選擇take all evens or all odds，只要不等于就必贏。等于就可以是tie，所以贏不了。

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

dp[i][j] 表示為 i 到 j 的區(qū)間中，把所有石子合并的最小花費(fèi)。在 i - j 的區(qū)間中，對(duì)于其中一點(diǎn)k，以 k 為最后合并的那個(gè)點(diǎn)，的score為 dp[i][k] + dp[k+1][j] + sum{i -> j}。所以對(duì)所有區(qū)間中的點(diǎn)取最小值。
通項(xiàng)公式為：

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 區(qū)間中，打爆所有氣球的最大coin數(shù)目。而針對(duì)區(qū)間中一點(diǎn) k，以k 為最后一點(diǎn)打爆，的coin數(shù)目 為
dp[i][k-1] + dp[k+1][k] + nums[i] * nums[left-1] * nums[right+1];

所以通項(xiàng)公式為：

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;
    }