区间DP
区间DP的特征: 可以两个或多个部分进行整合, 或者反过来；能将问题分解为能两两合并的形式.
区间DP的求解: 对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。
一般的方法是枚举长度(最外层L, 0 < L < N), 枚举左端点(第二层i, 0 < i < N-L), 以此可确定右端点(j = i + L), 枚举合并点 (i <= t < j).
什么是枚举合并点? 好比我要在一块蛋糕的第i厘米到第j厘米直接切一刀, 可以切在哪里? 在i~j之间下的那一刀就是合并点, 需要一个loop来枚举.
ACwin石子合并
设有N堆石子排成一排，其编号为1，2，3，…，N。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这N堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
例如有4堆石子分别为 1 3 5 2， 我们可以先合并1、2堆，代价为4，得到4 5 2， 又合并 1，2堆，代价为9，得到9 2 ，再合并得到11，总代价为4+9+11=24；
如果第二步是先合并2，3堆，则代价为7，得到4 7，最后一次合并代价为11，总代价为4+7+11=22。
- 思路
经典区间DP. 二维得相当标准.
这题会很容易记忆, 因为子问题是"合并第i个物体到第j个物体的最优解", 而原问题则是 "已合并第1个物体到第N个物体的最优解".
class Solution{
public int mergeStones(int[] a){
int[] arr = new int [a.length+1];
int N = a.length;
for(int i = 1;i <= N;i++){
arr[i] += a[i-1];
}
for(int i = 1;i <= N;i++){
arr[i] += arr[i-1];
}
//prefix sum
int [][] dp = new int [N+1][N+1];
for(int l = 2;l <= N;l++){ //枚举区间长度 - i到j之间的距离
for(int i = 1;i + l <= N+ 1;i++){ //枚举左端点
int j = i + l -1;
dp[i][j] = Integer.MAX_VALUE;
for(int k = i;k<j;k++){ //k是合并点, 此处枚举合并点, 从i到j之间都要考虑.
dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+(arr[j] - arr[i-1]));
}
}
}
return dp[1][N];
}
}
1000. Minimum Cost to Merge Stones
先枚举区间长度，再枚举区间起始点，然后枚举合并堆数，再枚举最后一个分割点。状态转移方程
class Solution:
def mergeStones(self, stones: List[int], K: int) -> int:
N = len(stones)
if (N - 1) % (K - 1) != 0:
return -1
pre = [0 for _ in range(N+1)]
pre[1] = stones[0]
for i in range(2, N+1):
pre[i] = pre[i-1] + stones[i-1]
dp = [[0 for k in range(N)] for j in range(N)]
for L in range(K, N+1):
for i in range(0, N-L+1):
j = i + L-1;
dp[i][j] = float('inf')
for mid in range(i, j, K-1):
dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid + 1][j])
if (j - i) % (K - 1) == 0:
dp[i][j] += (pre[j+1] - pre[i]);
return dp[0][N-1]
Burst balloon
Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[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 the maximum coins you can collect by bursting the balloons wisely.
Example:
Input: [3,1,5,8]
Output: 167
Explanation: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums = [1]+nums+[1]
N = len(nums)
dp = [[0 for i in range(N)] for j in range(N)]
for L in range(1, N):
for i in range(0, N-L):
j = i+L
for k in range(i+1, j):
dp[i][j] = max(dp[i][j], nums[i] * nums[k] * nums[j]+dp[i][k]+dp[k][j])
return dp[0][N-1]
回文相关的DP
- Palindrome Partitioning II
