區(qū)間DP
區(qū)間DP的特征: 可以?xún)蓚€(gè)或多個(gè)部分進(jìn)行整合, 或者反過(guò)來(lái)；能將問(wèn)題分解為能兩兩合并的形式.
區(qū)間DP的求解: 對(duì)整個(gè)問(wèn)題設(shè)最優(yōu)值屹篓，枚舉合并點(diǎn)，將問(wèn)題分解為左右兩個(gè)部分界拦，最后合并兩個(gè)部分的最優(yōu)值得到原問(wèn)題的最優(yōu)值乍楚。
一般的方法是枚舉長(zhǎng)度(最外層L, 0 < L < N), 枚舉左端點(diǎn)(第二層i, 0 < i < N-L), 以此可確定右端點(diǎn)(j = i + L), 枚舉合并點(diǎn) (i <= t < j).
什么是枚舉合并點(diǎn)? 好比我要在一塊蛋糕的第i厘米到第j厘米直接切一刀, 可以切在哪里? 在i~j之間下的那一刀就是合并點(diǎn), 需要一個(gè)loop來(lái)枚舉.
ACwin石子合并
設(shè)有N堆石子排成一排，其編號(hào)為1丛楚，2族壳，3，…趣些，N仿荆。
每堆石子有一定的質(zhì)量，可以用一個(gè)整數(shù)來(lái)描述坏平，現(xiàn)在要將這N堆石子合并成為一堆拢操。
每次只能合并相鄰的兩堆，合并的代價(jià)為這兩堆石子的質(zhì)量之和功茴，合并后與這兩堆石子相鄰的石子將和新堆相鄰庐冯，合并時(shí)由于選擇的順序不同孽亲，合并的總代價(jià)也不相同坎穿。
例如有4堆石子分別為 1 3 5 2， 我們可以先合并1、2堆玲昧，代價(jià)為4栖茉，得到4 5 2， 又合并 1孵延，2堆吕漂，代價(jià)為9，得到9 2 尘应，再合并得到11惶凝，總代價(jià)為4+9+11=24；
如果第二步是先合并2犬钢，3堆苍鲜，則代價(jià)為7，得到4 7玷犹，最后一次合并代價(jià)為11混滔，總代價(jià)為4+7+11=22。
- 思路
經(jīng)典區(qū)間DP. 二維得相當(dāng)標(biāo)準(zhǔn).
這題會(huì)很容易記憶, 因?yàn)樽訂?wèn)題是"合并第i個(gè)物體到第j個(gè)物體的最優(yōu)解", 而原問(wèn)題則是 "已合并第1個(gè)物體到第N個(gè)物體的最優(yōu)解".
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++){ //枚舉區(qū)間長(zhǎng)度 - i到j(luò)之間的距離
for(int i = 1;i + l <= N+ 1;i++){ //枚舉左端點(diǎn)
int j = i + l -1;
dp[i][j] = Integer.MAX_VALUE;
for(int k = i;k<j;k++){ //k是合并點(diǎn), 此處枚舉合并點(diǎn), 從i到j(luò)之間都要考慮.
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
先枚舉區(qū)間長(zhǎng)度歹颓，再枚舉區(qū)間起始點(diǎn)坯屿，然后枚舉合并堆數(shù)，再枚舉最后一個(gè)分割點(diǎn)巍扛。狀態(tài)轉(zhuǎn)移方程
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]
回文相關(guān)的DP
- Palindrome Partitioning II
