動態(tài)規(guī)劃（Dynamic Programming）
從分治到動態(tài)規(guī)劃：動態(tài)規(guī)劃的基本思想是將待求解的問題分解為若干個子問題妻率，這與分治的思想類似，
不同的地方在于當(dāng)子問題之間是相互獨立的鸠澈，這時候分治算法是我們解決問題的最好的思路，因為不同的子問題求解不會有公共的重復(fù)計算的地方蒂培，然而积糯，當(dāng)分解得到的子問題不相互獨立時绊茧，動態(tài)規(guī)劃就是我們最好的選擇铝宵，我們可以建立一個cache來記錄重復(fù)計算的部分，從而避免重復(fù)計算华畏。后面會講到這會使得一個多項式級別的問題變?yōu)榫€性的時間
關(guān)鍵點：找子問題鹏秋，如果一個問題具有無后效性，即后面的結(jié)果不會對前面的結(jié)果再次產(chǎn)生影響亡笑，可以選擇使用動態(tài)規(guī)劃侣夷。然而后面問題解的更改會倒置前面最優(yōu)解發(fā)生變化，比如：下圍棋仑乌，等策略游戲的編程就無法使用動態(tài)規(guī)劃百拓，一般采取回溯算法。
狀態(tài)轉(zhuǎn)移方程：這是動態(tài)規(guī)劃的核心晰甚，一般找出前面狀態(tài)的最優(yōu)解和當(dāng)前狀態(tài)最優(yōu)解的關(guān)系即為狀態(tài)轉(zhuǎn)移方程衙传。例如：最大子數(shù)組問題，我們可以找出前面以所有位置為結(jié)尾的最大子數(shù)組厕九，隨后求出最大的作為結(jié)果蓖捶；再比如：買股票，我們可以建模為：dp[i] 表示第i天將股票賣出可以獲得的最大利潤扁远，從而求得取所有子結(jié)果最大值作為全局最優(yōu)俊鱼；再比如：爬樓梯問題我們可以建模為 dp[i] = dp[i - 1] + dp[i - 2]表示第i次我可以選擇爬一層或者爬兩層來決定全局方案總數(shù)。
使用場景：一般的對于一個算法問題畅买，我們首先可以暴力求解并闲，觀察他的復(fù)雜度，如果這個復(fù)雜度是k^n復(fù)雜度谷羞，可以考慮優(yōu)化為O(nk)這時候一般會采取建立k維動態(tài)矩陣求解焙蚓。
可實施性：一般的對于k^n都的復(fù)雜度算法都可以看成當(dāng)前狀態(tài)和前面k個狀態(tài)有關(guān)，于是我們可以采用遞歸的方式（top down），然而這樣會導(dǎo)致下面的某個節(jié)點會被重復(fù)計算很多次购公，因為上方父節(jié)點會用到萌京，每用到一次，下方節(jié)點就需要重新計算一次宏浩，于是我們可以采用建立緩存記錄計算過的值或者就是我們所說的動態(tài)數(shù)組(bottom up)避免重復(fù)計算知残，從而大大地優(yōu)化了時間復(fù)雜度。舉例：斐波那契額數(shù)列通項式f(n) = f(n - 1) + f(n - 2)如果我們采用遞歸的方式解決比庄，會是O(2^n)的復(fù)雜度求妹，因為遞歸采取的是從f(n)計算到f(1), f(2)，回溯到f(n)佳窑，而我們采用動態(tài)數(shù)組``dp[i] = dp[i - 1] + dp[i - 2]即從前向后則可以使得前面的值得以記錄制恍。復(fù)雜度降為O(n)`
一維動規(guī)優(yōu)化
優(yōu)化點：空間的優(yōu)化，因為大多數(shù)問題我們通過動態(tài)方程可以看出神凑，當(dāng)前狀態(tài)只與前面的一個或者倆個狀態(tài)決定净神。如題目中所說三個問題: maxSubarray:dp[i] = max(dp[i - 1] + nums[i], nums[i])；sell stock: dp[i] = max(dp[i - 1] + nums[i] - nums[i - 1], 0);Climbing Stairs: dp[i] = dp[i - 1] + dp[i - 2]溉委。觀察這三個動態(tài)方程我們發(fā)現(xiàn)當(dāng)前狀態(tài)都是只與dp[i - 1]或者 dp[i - 2]有關(guān)鹃唯。于是我們可以考慮用指針來記錄前面的兩個或一個狀態(tài)點的值，從而完成當(dāng)前狀態(tài)的計算瓣喊。而不需要取申請數(shù)組坡慌。下面給出三個問題的原版和優(yōu)化版的解決方案：
- maxSubarray:
題目：
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
常規(guī)數(shù)組解法O(n)空間：
public int maxSubArray(int[] A) {
int n = A.length;
int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
dp[0] = A[0];
int max = dp[0];
for(int i = 1; i < n; i++){
dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
max = Math.max(max, dp[i]);
}
return max;
}
優(yōu)化為O(1)空間：
import sys
class Solution(object):
def maxSubArray(self, nums):
res = -sys.maxint
pre = 0
for i in nums:
if pre <= 0:
pre = i
res = max(res, pre)
else:
pre = pre + i
res = max(res, pre)
return res
- 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?
常規(guī)數(shù)組解法O(n)空間：
# Bottom up, O(n) space
def climbStairs2(self, n):
if n == 1:
return 1
res = [0 for i in xrange(n)]
res[0], res[1] = 1, 2
for i in xrange(2, n):
res[i] = res[i-1] + res[i-2]
return res[-1]
優(yōu)化為O(1)空間：
class Solution(object):
def climbStairs(self, n):
if n == 0:
return 0
if n == 1:
return 1
if n == 2:
return 2
pre = 2
prepre = 1
for i in xrange(n - 2):
tmp = pre + prepre
prepre = pre
pre = tmp
return pre
- sell stock
題目：
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0
In this case, no transaction is done, i.e. max profit = 0.
O(n)空間的思路可以讀者自己寫，給出O(1)的思路
import sys
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
n = len(prices)
if n <= 1:
return 0
res = 0
minP = prices[0]
for i in xrange(1, n):
res = max(res, prices[i] - minP)
minP = min(prices[i], minP)
return res
下期分析不能進行空間優(yōu)化的一維動態(tài)規(guī)劃藻三。有不足的地方請指正
轉(zhuǎn)載著名出處：http://www.reibang.com/p/62e54802d12c
