Matrix 跟Sequence的DP总结

Matrix的DP,二维数组

64 Minimum Path Sum: 对于每个点,只能往下走或者往右边走,所以每个点path sum的值来源于上面点或者左边点。
State: f[x][y]从起点走到x,y的最短路径
Function: f[x][y] = min(f[x-1][y], f[x][y-1]) + matrix[x][y]
initialize: f[0][0] = matrix[0][0], 对于二维数组要想f[i][0]跟f[0][i]如何初始化:
//f[i][0] = sum(0, 0 -> i, 0) 初始化最左边
//f[0][i] = sum(0, 0-> 0, i) 初始化最上边
Answer: f[n-1][m-1]

63 Unique Paths II,某些点不能走(obstacle),
不能走的点之间算为0就可以,用个if语句去check.

Sequence的DP,一维数组

State: f[i]表示”前i”个位置/数字/字母,
function: f[i]= f[j]….j是i之前的一个位置
initialize: f[0]..
answer: f[n-1]..

70 Climbing Stairs(爬楼梯)
state: f[i]表示前i个位置, 调到第i个位置的方案总数
function: f[i]=f[i-1]+f[i-2]
initialize:f[0]=1
answer: f[n]

  1. Jump Game
    state: f[i]表示能否从起点调到第i个位置
    function: f[i] = OR(f[j], j A[j] + j >= i && f[j]=true
    initialize: f[0]=true
    answer:f[n-1]

  2. Palindrome Partitioning II
    求最少的分割次数,
    state: f[i]为”前”i个字符组成的子字符串需要最少几次cut()
    function: f[i] = Min{f[j] + 1, j<i && j+1 ~ i 这段是一个palindrome}
    initialize: f[i]=i – 1(f[0]=0)
    answer:f[s.length()]

  3. Word Break
    state: f[i]为"前i"个字符能否被完美切分
    function: f[i]=OR{f[j], j<i, j+1 ~ i是一个词典中的单词}
    initialize: f[0]=true
    answer: f[s.length()]
    O(NL), N:字符串长度. L:最长单词的长度

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s