動態(tài)規(guī)劃（英語：Dynamic programming，簡稱DP）是一種在數(shù)學窄瘟、計算機科學跷坝、經(jīng)濟學和生物信息學中使用的侣诵，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。在生物信息領域边苹，比如在序列比對的時候陵且，就用到了動態(tài)規(guī)劃的思想。在隱馬爾科夫模型中的維特比 (Viterbi) 算法也使用了動態(tài)規(guī)劃算法个束。

對于一個問題慕购，我們分析出初始狀態(tài)和遞推公式是解出的關鍵。比如以下幾個經(jīng)典題目：

1. 爬樓梯 (https://leetcode.com/problems/climbing-stairs/)

有一座高度是10級臺階的樓梯茬底，從下往上走沪悲，每跨一步只能向上1級或者2級臺階。求出一共有多少種走法阱表。

這個問題仔細想想其實與斐波那契數(shù)列很像殿如，同樣可用遞歸求解。
假如最后我們已經(jīng)爬上了10層最爬，那么最后一個步驟走了要么一步涉馁， 要么兩步。也就是說爱致，我們到10層的走法烤送，其實就是我們走到八層和九層的方法的和。即F(n) = F(n-2) + F(n-1)糠悯。

遞歸求解：

def climb(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return climb(n - 1) + climb(n - 2)

climb(10)

遞歸會很慢帮坚，浪費很多沒必要的資源』グ可以考慮以下方法：

def climb(n):
    way = [0] * n
    way[0] = 1
    way[1] = 2
    for i in range(2, n):
        way[i] = way[i - 1] + way[i - 2]
    return way[n - 1]

# 或者 
def climb=(n):
    if n <= 2:
        return n
    else:
        a, b = 1, 2
        for i in range(n - 2):
            a, b = b, a + b
        return b

climb(10)

2. 使用最小花費爬樓梯 (https://leetcode.com/problems/min-cost-climbing-stairs/)

數(shù)組的每個索引做為一個階梯试和，第 i個階梯對應著一個非負數(shù)的體力花費值 cost[i](索引從0開始)。每當你爬上一個階梯你都要花費對應的體力花費值忘朝，然后你可以選擇繼續(xù)爬一個階梯或者爬兩個階梯灰署。您需要找到達到樓層頂部的最低花費。在開始時，你可以選擇從索引為 0 或 1 的元素作為初始階梯溉箕。(cost 的長度將會在 [2, 1000]晦墙。)
比如：

與上一個題有異曲同工之妙，其實其實本質(zhì)上i位置的值就等于前一個和前兩個中的最小值與這個位置的值的和肴茄，即f[i] = cost[i] + min(f[i-1], f[i-2])晌畅。

 def cal_cost(cost):
        dp = [0] * (len(cost) + 1)
        dp[0] = cost[0]
        dp[1] = cost[1]
        
        cost.append(0)
        for i in range(2, len(cost)):
            dp[i] = min(dp[i - 1], dp[i-2]) + cost[i]
            
        return dp[-1]

3. 打家劫舍 (https://leetcode.com/problems/house-robber/)

你是一個專業(yè)的小偷，計劃偷竊沿街的房屋寡痰。每間房內(nèi)都藏有一定的現(xiàn)金抗楔，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入拦坠，系統(tǒng)會自動報警连躏。
給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組，計算你在不觸動警報裝置的情況下贞滨，能夠偷竊到的最高金額入热。

當我們偷竊到第i家的時候，所能偷到的就是一直到第i - 1家所偷到的與第i - 2家和第i家偷到的錢的和的最大值晓铆，即dp[i] = max(nums[i] + dp[i -2], dp[i-1])勺良。

def rob(nums):
    size = len(nums)
    
    if size == 1:
        return nums[0]
    elif size == 2:
        return max(nums[0], nums[1])
    elif size == 0:
        return 0     
    else:
        dp = [0] * size
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])

        for i in range(2, size):
            dp[i] = max(nums[i] + dp[i - 2], dp[i - 1])

        return dp[-1]

其實可以發(fā)現(xiàn)我們其實只用到了dp[i-2]與dp[i-1]的值，那么對上邊的方法進行優(yōu)化：

def rob(nums):
    now = last = 0
    for i in range(len(nums)):
        now, last = max(last + nums[i], now), now 
    return now 

歡迎關注骄噪！