# Dynamic Programming - 動態規劃
動態規劃是一種「分治」的思想,通俗一點來說就是「大事化小,小事化無」的藝術。在將大問題化解為小問題的「分治」過程中,保存對這些小問題已經處理好的結果,并供后面處理更大規模的問題時直接使用這些結果。嗯,感覺講了和沒講一樣,還是不會使用動規的思想解題...
下面看看知乎上的熊大大對動規比較「正經」的描述。
> 動態規劃是通過拆分問題,定義問題狀態和狀態之間的關系,使得問題能夠以遞推(或者說分治)的方式去解決。
以上定義言簡意賅,可直接用于實戰指導,不愧是參加過NOI的。
動規的思想雖然好理解,但是要真正活用起來就需要下點功夫了。建議看看下面知乎上的回答。
動態規劃最重要的兩個要點:
1. 狀態(狀態不太好找,可先從轉化方程入手分析)
1. 狀態間的轉化方程(從題目的隱含條件出發尋找遞推關系)
其他的要點則是如初始化狀態的確定(由狀態和轉化方程得知),需要的結果(狀態轉移的終點)
動態規劃問題中一般從以下四個角度考慮:
1. 狀態(State)
1. 狀態間的轉移方程(Function)
1. 狀態的初始化(Initialization)
1. 返回結果(Answer)
動規適用的情形:
1. 最大值/最小值
1. 有無可行解
1. 求方案個數(如果需要列出所有方案,則一定不是動規,因為全部方案為指數級別復雜度,所有方案需要列出時往往用遞歸)
1. 給出的數據不可隨便調整位置
### 單序列([DP_Sequence](# "單序列動態規劃,通常使用 f[i] 表示前i個位置/數字/字母... 使用 f[n-1] 表示最后返回結果。"))
單序列動態規劃的狀態通常定義為:數組前 i 個位置, 數字, 字母 或者 以第i個為... 返回結果通常為數組的最后一個元素。
按照動態規劃的四要素,此類題可從以下四個角度分析。
1. State: f[i] 前i個位置/數字/字母...
1. Function: f[i] = f[i-1]... 找遞推關系
1. Initialization: 根據題意進行必要的初始化
1. Answer: f[n-1]
### 雙序列([DP_Two_Sequence](# "一般有兩個數組或者兩個字符串,計算其匹配關系. 通常可用 `f[i][j]`表示第一個數組的前 i 位和第二個數組的前 j 位的關系。"))
一般有兩個數組或者兩個字符串,計算其匹配關系。雙序列中常用二維數組表示狀態轉移關系,但往往可以使用滾動數組的方式對空間復雜度進行優化。舉個例子,以題 [Distinct Subsequences](http://algorithm.yuanbin.me/zh-cn/dynamic_programming/distinct_subsequences.html) 為例,狀態轉移方程如下:
~~~
f[i+1][j+1] = f[i][j+1] + f[i][j] (if S[i] == T[j])
f[i+1][j+1] = f[i][j+1] (if S[i] != T[j])
~~~
從以上轉移方程可以看出 `f[i+1][*]` 只與其前一個狀態 `f[i][*]` 有關,而對于 `f[*][j]` 來說則基于當前索引又與前一個索引有關,故我們以遞推的方式省略第一維的空間,并以第一維作為外循環,內循環為 j, 由遞推關系可知在使用滾動數組時,若內循環 j 仍然從小到大遍歷,那么對于 `f[j+1]` 來說它得到的 `f[j]` 則是當前一輪(`f[i+1][j]`)的值,并不是需要的 `f[i][j]` 的值。所以若想得到上一輪的結果,必須在內循環使用逆推的方式進行。文字表述比較模糊,可以自行畫一個二維矩陣的轉移矩陣來分析,認識到這一點非常重要。
小結一下,使用滾動數組的核心在于:
1. 狀態轉移矩陣中只能取 `f[i+1][*]` 和 `f[i][*]`, 這是使用滾動數組的前提。
1. 外循環使用 i, 內循環使用 j 并同時使用逆推,這是滾動數組使用的具體實踐。
代碼如下:
~~~
public class Solution {
/**
* @param S, T: Two string.
* @return: Count the number of distinct subsequences
*/
public int numDistinct(String S, String T) {
if (S == null || T == null) return 0;
if (S.length() < T.length()) return 0;
if (T.length() == 0) return 1;
int[] f = new int[T.length() + 1];
f[0] = 1;
for (int i = 0; i < S.length(); i++) {
for (int j = T.length() - 1; j >= 0; j--) {
if (S.charAt(i) == T.charAt(j)) {
f[j + 1] += f[j];
}
}
}
return f[T.length()];
}
}
~~~
紙上得來終覺淺,絕知此事要躬行。光說不練假把戲,下面就來幾道DP的題練練手。
### Reference
1. [什么是動態規劃?動態規劃的意義是什么? - 知乎](http://www.zhihu.com/question/23995189) - 熊大大和王勐的回答值得細看,適合作為動態規劃的科普和入門。維基百科上對動態規劃的描述感覺太過學術。
1. [動態規劃:從新手到專家](http://www.hawstein.com/posts/dp-novice-to-advanced.html) - Topcoder上的一篇譯作。
- Preface
- Part I - Basics
- Basics Data Structure
- String
- Linked List
- Binary Tree
- Huffman Compression
- Queue
- Heap
- Stack
- Set
- Map
- Graph
- Basics Sorting
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Heap Sort
- Bucket Sort
- Counting Sort
- Radix Sort
- Basics Algorithm
- Divide and Conquer
- Binary Search
- Math
- Greatest Common Divisor
- Prime
- Knapsack
- Probability
- Shuffle
- Basics Misc
- Bit Manipulation
- Part II - Coding
- String
- strStr
- Two Strings Are Anagrams
- Compare Strings
- Anagrams
- Longest Common Substring
- Rotate String
- Reverse Words in a String
- Valid Palindrome
- Longest Palindromic Substring
- Space Replacement
- Wildcard Matching
- Length of Last Word
- Count and Say
- Integer Array
- Remove Element
- Zero Sum Subarray
- Subarray Sum K
- Subarray Sum Closest
- Recover Rotated Sorted Array
- Product of Array Exclude Itself
- Partition Array
- First Missing Positive
- 2 Sum
- 3 Sum
- 3 Sum Closest
- Remove Duplicates from Sorted Array
- Remove Duplicates from Sorted Array II
- Merge Sorted Array
- Merge Sorted Array II
- Median
- Partition Array by Odd and Even
- Kth Largest Element
- Binary Search
- Binary Search
- Search Insert Position
- Search for a Range
- First Bad Version
- Search a 2D Matrix
- Search a 2D Matrix II
- Find Peak Element
- Search in Rotated Sorted Array
- Search in Rotated Sorted Array II
- Find Minimum in Rotated Sorted Array
- Find Minimum in Rotated Sorted Array II
- Median of two Sorted Arrays
- Sqrt x
- Wood Cut
- Math and Bit Manipulation
- Single Number
- Single Number II
- Single Number III
- O1 Check Power of 2
- Convert Integer A to Integer B
- Factorial Trailing Zeroes
- Unique Binary Search Trees
- Update Bits
- Fast Power
- Hash Function
- Count 1 in Binary
- Fibonacci
- A plus B Problem
- Print Numbers by Recursion
- Majority Number
- Majority Number II
- Majority Number III
- Digit Counts
- Ugly Number
- Plus One
- Linked List
- Remove Duplicates from Sorted List
- Remove Duplicates from Sorted List II
- Remove Duplicates from Unsorted List
- Partition List
- Two Lists Sum
- Two Lists Sum Advanced
- Remove Nth Node From End of List
- Linked List Cycle
- Linked List Cycle II
- Reverse Linked List
- Reverse Linked List II
- Merge Two Sorted Lists
- Merge k Sorted Lists
- Reorder List
- Copy List with Random Pointer
- Sort List
- Insertion Sort List
- Check if a singly linked list is palindrome
- Delete Node in the Middle of Singly Linked List
- Rotate List
- Swap Nodes in Pairs
- Remove Linked List Elements
- Binary Tree
- Binary Tree Preorder Traversal
- Binary Tree Inorder Traversal
- Binary Tree Postorder Traversal
- Binary Tree Level Order Traversal
- Binary Tree Level Order Traversal II
- Maximum Depth of Binary Tree
- Balanced Binary Tree
- Binary Tree Maximum Path Sum
- Lowest Common Ancestor
- Invert Binary Tree
- Diameter of a Binary Tree
- Construct Binary Tree from Preorder and Inorder Traversal
- Construct Binary Tree from Inorder and Postorder Traversal
- Subtree
- Binary Tree Zigzag Level Order Traversal
- Binary Tree Serialization
- Binary Search Tree
- Insert Node in a Binary Search Tree
- Validate Binary Search Tree
- Search Range in Binary Search Tree
- Convert Sorted Array to Binary Search Tree
- Convert Sorted List to Binary Search Tree
- Binary Search Tree Iterator
- Exhaustive Search
- Subsets
- Unique Subsets
- Permutations
- Unique Permutations
- Next Permutation
- Previous Permuation
- Unique Binary Search Trees II
- Permutation Index
- Permutation Index II
- Permutation Sequence
- Palindrome Partitioning
- Combinations
- Combination Sum
- Combination Sum II
- Minimum Depth of Binary Tree
- Word Search
- Dynamic Programming
- Triangle
- Backpack
- Backpack II
- Minimum Path Sum
- Unique Paths
- Unique Paths II
- Climbing Stairs
- Jump Game
- Word Break
- Longest Increasing Subsequence
- Palindrome Partitioning II
- Longest Common Subsequence
- Edit Distance
- Jump Game II
- Best Time to Buy and Sell Stock
- Best Time to Buy and Sell Stock II
- Best Time to Buy and Sell Stock III
- Best Time to Buy and Sell Stock IV
- Distinct Subsequences
- Interleaving String
- Maximum Subarray
- Maximum Subarray II
- Longest Increasing Continuous subsequence
- Longest Increasing Continuous subsequence II
- Graph
- Find the Connected Component in the Undirected Graph
- Route Between Two Nodes in Graph
- Topological Sorting
- Word Ladder
- Bipartial Graph Part I
- Data Structure
- Implement Queue by Two Stacks
- Min Stack
- Sliding Window Maximum
- Longest Words
- Heapify
- Problem Misc
- Nuts and Bolts Problem
- String to Integer
- Insert Interval
- Merge Intervals
- Minimum Subarray
- Matrix Zigzag Traversal
- Valid Sudoku
- Add Binary
- Reverse Integer
- Gray Code
- Find the Missing Number
- Minimum Window Substring
- Continuous Subarray Sum
- Continuous Subarray Sum II
- Longest Consecutive Sequence
- Part III - Contest
- Google APAC
- APAC 2015 Round B
- Problem A. Password Attacker
- Microsoft
- Microsoft 2015 April
- Problem A. Magic Box
- Problem B. Professor Q's Software
- Problem C. Islands Travel
- Problem D. Recruitment
- Microsoft 2015 April 2
- Problem A. Lucky Substrings
- Problem B. Numeric Keypad
- Problem C. Spring Outing
- Microsoft 2015 September 2
- Problem A. Farthest Point
- Appendix I Interview and Resume
- Interview
- Resume