动态规划专题
1.triangle
DFS-Traverse.png
用分治法
int divideConquer(int x,int y)
{
if (x == n)
{
return 0;
}
int left = A[x][y] + divideConquer(x+1,y);
int right = A[X][Y] + divideConquer(x+1,y+1);
return Math.min(left,right);
}
记忆化搜索
本质上:动态规划
动态规划就是解决了重复计算的搜索
动态规划的实现方式:1. 记忆化搜索2. 循环
1.png
2.png
用hash[x][y]记录曾经计算出的值
动态规划求解
down-top.png
top-down.png
此处可以把边界的f[i][0]和 f[i][i]初始化求出来，因为他们的值是固定的，后面就不用考虑不存在的问题了
2.Matrix DP
state: f[x][y] 表示我从起点走到坐标x,y......
function: 研究走到x,y这个点之前的一步intialize: 起点
answer: 终点
3.Sequence Dp
state: f[i]表示“前i”个位置/数字/字母,(以第i个为)...
function: f[i] = f[j] ... j 是i之前的一个位置intialize: f[0]..
answer: f[n-1]..
-
Climbing Stairs
state: f[i]表示前i个位置,跳到第i个位置的方案总数
function: f[i] = f[i-1] + f[i-2]
intialize: f[0] = 1
answer: f[n] - Jump game
- Jump game II
-
Longest Increasing Subsequence
state:
错误的方法: f[i]表示前i个数字中最长的LIS的长度
正确的方法: f[i]表示前i个数字中以第i个结尾的LIS的长度
function: f[i] = MAX{f[j]+1}, j < i && a[j] <= a[i])
intialize: f[0..n-1] = 1
answer: max(f[0..n-1]) -
word-break
canSegment[i]表示前i个字符串是否可分，lastWordLength代表已i结尾的后一个字符串长度，把整个字符串分成两段[0,i - lastWordLength-1]和[i - lastWordLength,i],如果这两段都可分，那么canSegment[i] = TRUE -
Palindrome Partitioning II
j可以表示前一段字符串长度，也可以表示已i结尾的字符串的长度。
在判断[i,j]之间的字符串是不是回文串，可以根据[i+1,j-1]是不是且s[i]==[j]否。
4.Two Sequences Dp
state: f[i][j]代表了第一个sequence的前i个数字/字符 配上第二个sequence的前j个...
function: f[i][j] = 研究第i个和第j个的匹配关系intialize: f[i][0] 和 f[0][i]
answer: f[s1.length()][s2.length()]
-
Edit Distance
state: f[i][j]a的前i个字符“配上”b的前j个字符最少要用几次编辑使得他们相等
function:
f[i][j] = MIN(f[i-1][j-1], f[i-1][j]+1, f[i][j-1]+1) // a[i] == b[j]
= MIN(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1 // a[i] != b[j]intialize: f[i][0] = i, f[0][j] = j
answer: f[a.length()][b.length()] -
Longest Common Subsequence
state: f[i][j]表示前i个字符配上前j个字符的LCS的长度
function: f[i][j] = f[i-1][j-1] + 1 // a[i] == b[j]
= MAX(f[i-1][j], f[i][j-1]) // a[i] != b[j]intialize: f[i][0] = 0
f[0][j] = 0
answer: f[a.length()][b.length()] -
Longest Common Substring
state: f[i][j]表示前i个字符配上前j个字符的LCS‘的长度(一定以第i个和第j个结尾的LCS’)
function: f[i][j] = f[i-1][j-1] + 1 // a[i] == b[j]= 0 // a[i] != b[j]
intialize: f[i][0] = 0f[0][j] = 0
answer: MAX(f[0..a.length()][0..b.length()]) - Distinct Subsequence
- Interleaving String
5. Backpack
-
Backpack
n个整数a[1..n],装m的背包state: f[i][j] “前i”个数,取出一些能否组成和为j
function: f[i][j] = f[i-1][j - a[i]] or f[i-1][j]
intialize: f[X][0] = true; f[0][1..m] = false
answer: 能够使得f[n][X]最大的X(0<=X<=m) -
Backpack II
n个物品,背包为m,体积a[1..n],价值v[1..n]
state: f[i][j]表示前i个物品中,取出“若干”物品
后,体积“正好”为j的最大价值。
function: f[i][j] = max{f[i-1][j], f[i-1][j - a[i]] + v[i]}
intialize: f[X][0] = 0, f[0][1..m] = -oo
answer: f[n][1..m]中最大值 -
k Sum
state: f[i][j][t]前i个数取j个数出来能否和为tfunction: f[i][j][t] = f[i - 1][j - 1][t - a[i]] or f[i - 1][j][t]
1.问是否可行 (DP) - f[x][0][0] = true
2.问方案总数 (DP) - f[x][0][0] = 1
3.问所有方案 (递归/搜索) -
Minimum Adjustment Cost
n个数,可以对每个数字进行调整,使得相邻的两个数的差都<=target, 调整的费用为
Sigma(|A[i]-B[i]|)
A[i]原来的序列 B[i]是调整后的序列A[i] < 200, target < 200让代价最小
state: f[i][v] 前i个数,第i个数调整为v,满足相邻两数<=target,所需要的最小代价
function: f[i][v] = min(f[i-1][v’] + |A[i]-v|, |v-v’| <= target)
intialize: f[1][A[1]] = 0, f[1][A[1] +- X] = X
answer: f[n][X]O(n * A * T)
