先挖个坑,今天听了两个小时的DP,深有收获,先把笔记贴在这里。过阵子来整理。。。
1 DP适用的题目:
-求最值Jump Game IIPalindrome Partitioning
IIEdit DistanceMinimum Path SumTriangle
-可行不可行 Jump GameWord BreakInterleaving
String
-求方案总数 eg:Climbing StairsDecode WaysDistinct
SubsequencesUnique PathsUnique Paths II
但是如果要求具体每个方案:DFS eg:Combination SumCombination Sum II
2 DP的分类:
Sequence DP
Q1. Climbing Stairs
http://oj.leetcode.com/<wbr>problems/climbing-stairs/</wbr>
Q2. Decode Ways
http://oj.leetcode.com/<wbr>problems/decode-ways/</wbr>
Q3. Jump Game I, II
http://oj.leetcode.com/<wbr>problems/jump-game/</wbr>
http://oj.leetcode.com/<wbr>problems/jump-game-ii/</wbr>
Q4. Palindrome Patitioning II
http://oj.leetcode.com/<wbr>problems/palindrome-<wbr>partitioning-ii/</wbr></wbr>
Q5. Word Break
http://oj.leetcode.com/<wbr>problems/word-break/</wbr>
Two Sequences DP
Q6. Distinct Subsequences
http://oj.leetcode.com/<wbr>problems/distinct-<wbr>subsequences/</wbr></wbr>
Q7. Edit Distance
http://oj.leetcode.com/<wbr>problems/edit-distance/</wbr>
Q8. Interleaving String (Review)
http://oj.leetcode.com/<wbr>problems/interleaving-string/</wbr>
Matrix DP
Q9. Minimum Path Sum
http://oj.leetcode.com/<wbr>problems/minimum-path-sum/</wbr>
Q10. Triangle
http://oj.leetcode.com/<wbr>problems/triangle/</wbr>
Q11. Unique Path I, II
http://oj.leetcode.com/<wbr>problems/unique-paths/</wbr>
http://oj.leetcode.com/<wbr>problems/unique-paths-ii/</wbr>
3 DP的几个要素:
1找状态status意义!
// Matrix: f[i][j] 表示从1,1走到i,j
// sequence: f[i] 表示前i个。。。
// 2 sequence: f[i][j] 表示前i个匹配上前j个
// interval:f[i][j] 表示区间i->j
2 转移方程
LCS:f[i][j] = max(f[i-1][j],f[i][j-1], f[i-1][j-1]+1) 假设有两个字符串a[0...i...m], b[0...j...n],f[i][j]表示a[0...i]和b[0...j] 的最长公共子序列的长度。
f[i][j]的值决定于3种情况:
1)a[i] == a[j] 则说明可以在f[i-1][j-1]的基础上拓展出一个公共的字符,即f[i][j] = f[i-1][j-1] + 1
2)a[i] != a[j] 则说明此时,a[0...i]和b[0...j]的最长公共子序列中绝对不可能同时包含a[i]和b[j]。则a[0...i]和b[0...j]的最长公共子序列可能以a[i]结尾,也可能以b[j]结尾,还可能结尾不包含a[i]或b[j]
这三种情况,其实对应的是:
可能以a[i]结尾:f[i][j-1]
可能以b[j]结尾:f[i-1][j]
可能结尾不包含a[i]或b[j]:f[i-1][j-1]
现在我们要求的是这三种情况的最大值:f[i][j] = max(f[i][j-1], f[i-1][j], f[i-1][j-1])
(注:第三种情况的值必然小等于前面两种情况的值,因为在计算f[i][j-1]和f[i-1][j]时,已经考虑过f[i-1][j-1]而选的最大值,所以f[i-1][j-1]必然不会大于前两种值!可以不用比较)
所以可以简化成:f[i][j] = max(f[i][j-1], f[i-1][j])
最后写成的代码是:http://blog.csdn.net/fightforyourdream/article/details/20015641
LIS:f[i]=max(f[j]+1, a[i]>=a[j]) 分析最后一次划分,最后一次字符/最后一个。。
3 初始化 // f[i][0] f[0][i]
// f[0]
// lis: f[1..N] = 1
4 答案是什么 // LIS: max{f[i]}
// LCS: f[n][m]
5 Loop怎么写
// interval: 区间从小到大,先枚举区间长度,palindrome partitioning II
初始化
matrix DP
sequence DP
LIS
for(i=0; i<n; i++){
for(j=0; j<i; j++) 位置或长度
if(a[i]>a[j]){
f[i] = max(f[i], f[j]+1)
}
}
开始多开一位,把0位空出来
2 sequence DP
LCS Edit distance
dist[i][j]代表word1的前i个字符 匹配上 word2的前j个字符 的最XXX
LCS
interleave[i][j]代表s1的前i个字符,和s2的前j个字符,是否能匹配s3的前i+j字符
打擂台
======================================
分享到:
相关推荐
高中政治会考知识点及总结_(整理过的重点).pdf
高中政治会考知识点总结高中会考政治复习资料.doc
好-高中生物会考知识点总结.doc
高中物理会考公式总结.doc
高中会考化学知识点总结.doc
高中政治会考易错知识归纳总结.pdf
高中政治会考知识点提纲总结.docx
高中化学会考复习总结总结.doc
高二会考政治知识点总结五篇2.doc
政治-高中政治会考易错知识归纳总结.docx
高中物理会考知识点总结打印.doc
政治-九年级政治会考必背知识要点总结.docx
政治-初二下册政治会考复习提纲资料总结.docx
高中通用技术会考高考知识点总结与归纳整理.pdf
java面试常见的问题,对于要想从事java工程师的初学者一个很好的宝典哦。
高中通用技术山东会考知识点总结.pdf
公务员面试经常会考的题.doc
高二政治会考复习知识点总结【必修1-必修4】.pdf