动态规划算法学习
? 筆試面試中經常會出現一些考察動態規劃方面的題目，以前沒有接觸過，現在初學做個整理。
1. 什么是動態規劃？
???????? 和分治法一樣，動態規劃（dynamicprogramming）是通過組合子問題而解決整個問題的解。
???????? 分治法是將問題劃分成一些獨立的子問題，遞歸地求解各子問題，然后合并子問題的解。
???????? 動態規劃適用于子問題不是獨立的情況，也就是各子問題包含公共的子子問題。
???????? 此時，分治法會做許多不必要的工作，即重復地求解公共的子問題。動態規劃算法對每個子問題只求解一次，將其結果保存起來，從而避免每次遇到各個子問題時重新計算答案。
2. 動態規劃算法的設計
兩種方法：
???????? 自頂向下（又稱記憶化搜索、備忘錄）：基本上對應著遞歸函數實現，從大范圍開始計算，要注意不斷保存中間結果，避免重復計算
???????? 自底向上（遞推）：從小范圍遞推計算到大范圍
動態規劃的重點：
???????? 遞歸方程+邊界條件
3. 爬樓梯問題
???????? 一個人每次只能走一層樓梯或者兩層樓梯，問走到第80層樓梯一共有多少種方法。
???????? 設DP[i]為走到第i層一共有多少種方法，那么DP[80]即為所求。很顯然DP[1]=1, DP[2]=2（走到第一層只有一種方法：就是走一層樓梯；走到第二層有兩種方法：走兩次一層樓梯或者走一次兩層樓梯）。同理，走到第i層樓梯，可以從i-1層走一層，或者從i-2走兩層。很容易得到：
???????? 遞推公式：DP[i]=DP[i-1]+DP[i-2]
???????? 邊界條件：DP[1]=1?? DP[2]=2
???????? (a)自頂向下的解法：
???????? (b)自底向上的解法：
[cpp]?view plaincopy 4. 最長上升子序列
???????? 對于序列：4 1 2 24，它的最長上升子序列是1 2 4，長度為3。
???????? 對于序列：4 2 4 25 6，它的最長上升子序列是2 4 5 6，長度為4
???????? 設a[i]表示原序列，設DP[i]表示以第i個數結尾的最長上升序列的長度，那么很顯然想導出DP[i]的值，需要在DP[k](1<=k<i)中找出滿足a[k]<a[i]最大的一項。假設第kk項是我們找到的答案，那么第i個數就可以接在第kk個數之后，成為以第i個數結尾的最長升序列。如果沒有找到答案，換言之第i個數比前面的數都要小，那么DP[i]=1，也即生成了從自己開始又以自己結尾的最長升序列。綜上，我們很容易得出：
???????? 遞推公式：DP[i]=max(DP[k]+1,DP[i])? 1<=k<i
???????? 邊界條件：DP[i]=1?????????????????? 1<=i<=n
???????? 算法復雜度為O(n^2)
5. 最長公共子序列
???????? 給定兩個序列X和Y，稱序列Z是X和Y的公共子序列如果Z既是X的一個子序列，又是Y的一個子序列。例如，如果X={a,b,c,b,d,a,b} Y={b,d,c,a,b,a} 那么序列{b,c,a}就是X和Y的一個公共子序列，但是它并不是X和Y的最長公共子序列，因為它的長度為3。而同為X和Y公共子序列的{b,c,b,a}，長度為4，因為找不到長度為5或更大的公共子序列，所以X和Y的最長公共子序列長度就為4。
???????? 假設兩個序列數組分別為a，b。定義f(i,j)為計算到a數組第i個數、b數組第j個數時所得到的最長公共子序列的長度。這時有兩種情況：
???????? 1.假如a[i]=b[j]，那么f(i,j)=f(i-1,j-1)+1
???????? 2.假如a[i]!=b[j]，那么f(i,j)=max(f(i-1,j),f(i,j-1))
???????? 邊界條件為：f(i,0)=0???? 1<=i<=len(a)
?????????????????????????????? f(0,j)=0???? 1<=j<=len(b)
???????? 算法復雜度：O(n^2)，len(a)表示數組a的長度。
總結
- 上一篇： 全排列（含递归和非递归的解法）
- 下一篇： Python算法：动态规划