演算法 - Dynamic Programming
中文譯作「動態規劃」，英文縮寫為 DP 。
在數學領域中， programming 是指「最佳化（ optimization ）」的意思，例如求極大值、求極小值。
dynamic 是指「動態」的意思。
顧名思義， Dynamic Programming 是一個以動態的方式來進行最佳化的方法。
DP = Divide and Conquer + Memoization
DP 可視做是 Divide and Conquer 的延伸版本
當運用 Divide and Conquer 所遞迴分割出來的子問題都非常相像的時候
並且當同樣的子問題一而再、再而三出現的時候
──就運用 Memoization 儲存全部子問題的答案，節省重複計算相同問題的時間，以空間來換取時間。
由於全部子問題的答案都儲存在記憶體的緣故，
計算答案的過程，就是反覆不斷地在各塊記憶體中讀取數據、計算數據、儲存數據，
動感地達成最佳化──動態規劃之名由此而來。
用 Dynamic Programming 設計演算法時的步驟
利用Divide and Conquer把原問題遞迴地分成許多更小的問題。（recurrence）
甲、子問題與原問題的求解方式皆類似。（optimal sub-structure）
乙、子問題會一而再、再而三的出現。（overlapping sub-problems）先找到原問題和其子問題們之間的關係，寫出遞迴公式。如此一來，便可利用遞迴公式，用子子問題的答案，求出子問題的答案；用子問題的答案，求出原問題的答案。
確認每個問題需要哪些子問題來計算答案，並確認總共有哪些子問題。（state space）
確認可能出現的子問題全部共有哪些，這樣才能知道要計算哪些子問題，才能知道共會花多少時間、多少記憶體。
決定各個問題的計算先後次序。（computational sequence）
有了遞迴公式和表格結構之後，就必須安排出一套計算的順序。大問題的答案，總是以小問題的答案來求得的，所以，小問題的答案是必須先算的，否則大問題的答案從何而來呢？我們會利用較小問題的答案，計算出較大問題的答案
──因此，一個好的安排方式，不但會使程式碼容易撰寫，還可有效節省記憶體空間，甚至重複利用記憶體空間。安排好各個問題的答案，要存放在表格的哪個位置。（lookup table）
實作 DP 的程式時，會建立一個表格，在表格存入所有大小問題的答案。安排好每個問題的答案在表格的哪個位置，這樣計算時才能知道該在哪裡取值。這個表格其實就是所謂的 lookup table 。
實做程式，主要有兩種方式：
- Top-down, Recursive.
- Bottom-up, Iterative.
撰寫程式碼的時候，應小心下面幾項問題:
初始值：記得先將最小、最先被計算的子問題，將其答案預先算好，內建於程式碼中，並存入表格。一道遞迴公式必須擁有初始值，才有辦法計算其他項。
表格界限：切勿存取超出表格界限的地方。計算過程中，一旦子問題的答案出錯，就會如骨牌效應般一個影響一個，造成很難除錯。
計算順序：切勿存取還沒計算過答案的子問題，原因同前項所述。
Leetcode舉例一：Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
1 | Example 1: |
1 | Example 2: |
思路：
到達n層，有兩種方式：
從N-1上一步，或者從N-2上兩部，所以這就是一個斐波那契數列。
遞推公式：f(n) = f(n-1) + f(n - 2);1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution {
public int climbStairs(int n) {
int[] a = new int[n + 1];
a[0] = 0;
if (n > 0) {
a[1] = 1;
}
if (n > 1) {
a[2] = 2;
}
if (n >= 3) {
for (int i = 3; i < a.length; i++) {
a[i] = a[i - 1] + a[i - 2];
}
}
return a[n];
}
}
Leetcode舉例二：Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
1 | Example: |
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
思路：
思考時，首先想到的是暴力法，即從第一個成員開始，長度從1遞增，計算各位成員之和並比較，保留其中的最大值。
這種做法的覆雜度高達O(N^2)，毫無疑問在大規模用例時會超時。
此題將求解特定子數組的問題轉換成了求解截止i (0<=i<=nums.size())( 必須包括nums[i] )的子數組的最大和”
以示例中的例子進行說明，用數組dp[ ]表示子問題的解：dp[0]=-2 此時只有一個元素dp[1]=1 由於-2<1，因此截止位置1的子數組的最大和為1dp[2]=-2 首先需要說明的是，該子數組必須包含末位nums[i]=nums[2]=-3，至於為什麽這樣，後面會再作解釋。
由於相比dp[i-1]，只增加了一位，因此只要判斷前面一位的dp是大於0還是小於0，若大於0，則對於此處的dp是“有益的”，需將它包含進去，否則就捨棄，只計nums[ i ]即可。
由於dp[1]=1>0，dp[2]=dp[1]+nums[2]=1+(-3)=-2
dp[3]=4 由於dp[2]=-2<0，故dp[3]=nums[3]=4dp[4]=3 4-1dp[5]=5 3+2dp[6]=6 5+1dp[7]=1 6-5dp[8]=5 1+4
迭代公式為：dp[i]=(dp[i-1]>0?dp[i-1]:0)+nums[i];
顯而易見，dp數組的最大值就是子數組和的最大值。
回過頭來也可以理解為什麽一定要將nums[i]的值計算進去：
因為題目要求子數組中所有成員位置上必須是左右相鄰的，如果不將nums[i]的值強行包含進去，
則可能出現最優解在後面但搜索不到的情形。
完整Solution如下：1
2
3
4
5
6
7
8
9
10
11
12public int maxSubArray(int[] A) {
int[] dp = new int[A.length]; //dp[i] means the maximum subarray ending with A[i];
dp[0] = A[0];
int maxx = dp[0];
for(int i = 1; i < A.length; i++){
dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
max = Math.max(maxx, dp[i]);
}
return max;
}
Leetcode舉例三：House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
1 | Example 1: |
1 | Example 2: |
思路：
這道題的本質相當於在一列數組中取出一個或多個不相鄰數，使其和最大。
我們對於這類求極值的問題首先考慮動態規劃Dynamic Programming來解，我們維護一個一位數組dp，
其中dp[i]表示到i位置時不相鄰數能形成的最大和，那麽遞推公式怎麽寫呢？
我們先拿一個簡單的例子來分析一下，比如說nums為{3, 2, 1, 5}，那麽我們來看我們的dp數組應該是什麽樣的，首先dp[0]=3沒疑問，再看dp[1]是多少呢，由於3比2大，所以我們搶第一個房子的3，當前房子的2不搶，所以dp[1]=3，再來看dp[2]，由於不能搶相鄰的，所以我們可以用再前面的一個的dp值加上當前的房間值，和當前房間的前面一個dp值比較，取較大值當做當前dp值，所以我們可以得到遞推公式dp[i] = max(num[i] + dp[i - 2], dp[i - 1]), 由此看出我們需要初始化dp[0]和dp[1]，其中dp[0]即為num[0]，dp[1]此時應該為max(num[0], num[1])，代碼如下：
完整Solution:
1 | public class Main { |
Leetcode舉例三延伸：House Robber 2
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
1 | Example 1: |
1 | Example 2: |
思路:
Since every house is either robbed or not robbed and at least half of the houses are not robbed, the solution is simply the larger of two cases with consecutive houses, i.e. house i not robbed, break the circle, solve it, or house i + 1 not robbed. Hence, the following solution. I chose i = n and i + 1 = 0 for simpler coding. But, you can choose whichever two consecutive ones.
Solution:
1 | class Solution { |