動態(tài)規(guī)劃專題

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

記憶化搜索

本質(zhì)上:動態(tài)規(guī)劃
動態(tài)規(guī)劃就是解決了重復計算的搜索
動態(tài)規(guī)劃的實現(xiàn)方式:1. 記憶化搜索2. 循環(huán)

1.png

2.png

用hash[x][y]記錄曾經(jīng)計算出的值

動態(tài)規(guī)劃求解

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: 終點

• Minimum Path Sum
• Unique Paths
• Unique Paths II

3.Sequence Dp

state: f[i]表示“前i”個位置/數(shù)字/字母,(以第i個為)...
function: f[i] = f[j] ... j 是i之前的一個位置intialize: f[0]..
answer: f[n-1]..

• Climbing Stairs
  state: f[i]表示前i個位置,跳到第i個位置的方案總數(shù)
  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個數(shù)字中最長的LIS的長度
  正確的方法: f[i]表示前i個數(shù)字中以第i個結(jié)尾的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結(jié)尾的后一個字符串長度，把整個字符串分成兩段[0,i - lastWordLength-1]和[i - lastWordLength,i],如果這兩段都可分，那么canSegment[i] = TRUE
• Palindrome Partitioning II
  j可以表示前一段字符串長度，也可以表示已i結(jié)尾的字符串的長度。
  在判斷[i,j]之間的字符串是不是回文串，可以根據(jù)[i+1,j-1]是不是且s[i]==[j]否。

4.Two Sequences Dp

state: f[i][j]代表了第一個sequence的前i個數(shù)字/字符 配上第二個sequence的前j個...
function: f[i][j] = 研究第i個和第j個的匹配關(guān)系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個結(jié)尾的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個整數(shù)a[1..n],裝m的背包state: f[i][j] “前i”個數(shù),取出一些能否組成和為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個數(shù)取j個數(shù)出來能否和為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.問方案總數(shù) (DP) - f[x][0][0] = 1
  3.問所有方案 (遞歸/搜索)
• Minimum Adjustment Cost
  n個數(shù),可以對每個數(shù)字進行調(diào)整,使得相鄰的兩個數(shù)的差都<=target, 調(diào)整的費用為
  Sigma(|A[i]-B[i]|)
  A[i]原來的序列 B[i]是調(diào)整后的序列A[i] < 200, target < 200讓代價最小
  state: f[i][v] 前i個數(shù),第i個數(shù)調(diào)整為v,滿足相鄰兩數(shù)<=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)