区间类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;
}
