九章 Dynamic Programming

九章 Dynamic Programming



// 从x，y出发，往下走的所有路径中，最小路径的权重之和是多少
int dfs(int x, int y) {
  if (x == n) {
    return 0;
  }
  if (hash[x][y] != -1) {
    return hash[x][y];
  }

  hash[x][y] = min(dfs(x+1, y), dfs(x+1, y+1)) + a[x][y];
  return hash[x][y];
}

dfs(0,0);
O(2^n)

(1, 0) -> (2,0), *(2,1)
(1,1) -> *(2, 1), (2,2)
O(n^2)
//记忆化搜索 Memorize Search

DP -> 记忆化搜索

//for
state: f[x][y] 表示从0,0出发， 到达x，y这个点的最短路径长度
function: f[x][y] = min(f[x-1][y], f[x-1][y-1]) + a[x][y];


动态规划的4点要素
1.状态State（灵感，创造力，存储小规模问题的结果）
2. 方程Function （状态之间的联系，怎么通过小的状态，来算大的状态）
3. 初始化 Initialization （最极限的小状态是什么，起点）
4. 答案 Answer （最大的那个状态是什么，终点）

Recursive VS DP
递归是一种程序的实现，方式是函数的自我调用
Function(x) {
  ...
  Function(x-1)
  ...
}
动态规划是一种解决问题的思想：大规模问题的结果，是由小规模问题的结果运算得到。动态规划可以用递归来实现(Memorization Search)

面试最常见的四种类型
1. Matrix DP（10%）
2. Sequence (40%)
3. Two Sequences DP (40%)
4. Backpack (10%)

如何想到使用DP
1. One of the following three:
a) Find a maximum/minimum result
b) yes/no
c) count all possible solutions
2. Can not sort (Can not swap)
   longest consecutive sequence

1. Matrix DP （triangle， unique path， Minimum Path Sum，...）
state: f[x][y] 表示从起点走到坐标x，y。。。。。。
function：研究最后一步怎么走
initialize：起点f[0][0] // f[0][i] f[i][0]
answer: 终点

2. Sequence DP （climbing stairs, jump game，Palindrome Partition II， word break，longest increasing subsequence）
state：f[i]表示“前i”个位置，数字，字母(以第i个为）。。。
function：f[i] = f[j]... j是i之前的一个位置
initialize: f[0]..
answer: f[n-1]..

3. Two sequence DP （longest common subsequence， longest common substring， edit distance, distince subsequence, interleaving string)
state：f[i][j]代表了第一个sequence的前i个数字，字符配上第二个sequence的前jge
function：f[i][j]=研究第i个和第j个的匹配关系
initilize：f[i][0]和f[0][i]
answer：f[s1.length()][s2.length()]

4. Backpack
题目：给n个正整数，一个数target，问能否从n个数中却出若干个数，他们的和为target
state：f[i][s]前i个数字，取出一些能否组成和为s
function：f[i][s]=f[i-1][S-a[i]] or f[i-1][s]
initialize:f[0][0]=true;f[0][1...SUM]=false
answer:f[n][target]

K Sum
n个数，取k个数，组成和为target
state：f[i][j][t]前i个数取j个数出来能否和为t
function:f[i][j][t] = f[i-1][j-1][t-a[i]] or f[i-1[j][t]
1.问是否可行（DP）
2.问方案总数 （DP）
3. 问所有方案（递归、搜索）

最小调整代价
n个数，可以对每个数字进行调整，使得相邻两个数的差都是小于target，调整的费用为
sigma（A[i]-B[i])
A[i]
A[i] < 200, target < 200
让代价最小
O（n*200*target）
state：f[i][v]前i个数，第i个数调整为v，满足相邻两个数小于等于target，所需要的最小代价
function：f[i][v] = min(f[i-1][v'] + |A[i] - v|, |v-v"|< target)