[笔记整理] 九章算法第五章 Dynamic Programming

1. 如何想到使用DP？
(1) Cannot sort
(2) One of the following three:
a) Find minimum/maximum result
b) Decide whether something is possible or not
c) Count all possible solutions

2. DP题目分类
2.1 Matrix DP
(1) Unique Path
http://codechen.blogspot.com/2016/07/leetcode-114-unique-path.html
(2) Unique Path II
http://codechen.blogspot.com/2016/07/leetcode-63-unique-paths-ii.html
(3) Minimum Path Sum
http://codechen.blogspot.com/2016/07/leetcode-64-minimum-path-sum.html

2.2 Sequence DP
(1) Climbing Stairs
http://codechen.blogspot.com/2016/07/leetcode-70-climbing-stairs.html
(2) Jump Game
http://codechen.blogspot.com/2016/07/leetcode-55-jump-game.html
(3) Jump Game II
(4) Palindrome Partitioning II
http://codechen.blogspot.com/2016/07/lintcode-108-palindrome-partitioning-ii.html
(5) Word Break
http://codechen.blogspot.com/2016/07/leetcode-139-word-break.html
* Word Break II (Not DP problem, use recursion + pruning)
http://codechen.blogspot.com/2016/08/leetcode-140-word-break-ii.html
(6) Longest Increasing Subsequence
http://codechen.blogspot.com/2016/08/leetcode-300-longest-increasing.html
(7) Combination Sum IV
http://codechen.blogspot.com/2016/07/leetcode-377-combination-sum-iv.html

2.3 Two Sequence DP
(1) Longest Common Subsequence
http://codechen.blogspot.com/2016/08/lintcode-77-longest-common-subsequence.html
(2) Longest Common Substring
http://codechen.blogspot.com/2016/08/lintcode-79-longest-common-substring.html
(3) Edit Distance
http://codechen.blogspot.com/2016/08/lintcode-119-edit-distance.html
(4) Distinct Subsequences
http://codechen.blogspot.com/2016/08/leetcode-115-distinct-subsequences.html
(5) Interleaving String
http://codechen.blogspot.com/2016/08/leetcode-29-interleaving-string.html

2.4 Backpack
(1) K Sum
http://codechen.blogspot.com/2016/08/lintcode-89-k-sum.html
(2) 最小调整代价
 n 个数，可以对每个数字进行调整，使得相邻2个数的插都<target，调整费用为:
        sigma(|A[i] - B[i]|), A为原序列,B为调整后的序列;
求最小调整代价