動態規劃步步為營之[遞推]->[記憶化]->[動態規劃]
- 2019 年 10 月 6 日
- 筆記
動態規劃步步為營之[遞推]->[記憶化]->[動態規劃]
0.導語
今日步步為營，實戰dp，採用遞推、記憶化、動態規劃，三種方法解決兩道題目，並深入研究動態規劃套路。
今日題目
- 爬樓梯
- 三角形最小路徑和
1.爬樓梯
題目描述
假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個正整數。
示例 1：
輸入： 2 輸出： 2 解釋： 有兩種方法可以爬到樓頂。 1. 1 階 + 1 階 2. 2 階
示例 2：
輸入： 3 輸出： 3 解釋： 有三種方法可以爬到樓頂。 1. 1 階 + 1 階 + 1 階 2. 1 階 + 2 階 3. 2 階 + 1 階
思路
這裡爬樓梯每次可以爬1個或2個台階，也就是說當前的結果與前面和前面的前面有關，所以得到下面遞推式：
res[i] = res[i - 1] + res[i - 2]
方法一：遞歸法
class Solution(object): def climbStairs(self,n): if n == 0 or n == 1: return 1 else: return self.climbStairs(n - 1) + self.climbStairs(n - 2)
方法二：記憶化搜索
但是這樣做存在著大量的重複運算。我們可以通過記憶化搜索的方式來優化上面的問題。
class Solution(object): def climbStairs(self,n): mem = [0]*(n+1) return self._climbStairs(n,mem) def _climbStairs(self,n,mem): if n==0 or n==1: return 1 if mem[n]: return mem[n] mem[n] = self._climbStairs(n-1,mem)+self._climbStairs(n-2,mem) return mem[n]
方法三：動態規劃
class Solution(object): def climbStairs(self,n): res = [0] * (n + 1) res[0] = 1 res[1] = 1 for i in range(2, n + 1): res[i] = res[i - 1] + res[i - 2] return res[n]
優化版
在Python中直接可以對兩個數據進行交換，而不需要新增一個temp變數。
例如：
x, y = 1, 2 print(x, y) x, y = y, x # 交換同時進行 print(x, y)
上述的x,y=y,x中x與y同時進行！
def climbStairs2(n): x, y = 1, 1 for _ in range(1, n): x, y = y, x + y return y
2.三角形最小路徑和
題目描述
給定一個三角形，找出自頂向下的最小路徑和。每一步只能移動到下一行中相鄰的結點上。
例如，給定三角形：
[ [2], [3,4], [6,5,7], [4,1,8,3] ]
自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11）。
說明：
如果你可以只使用 O(n) 的額外空間（n 為三角形的總行數）來解決這個問題，那麼你的演算法會很加分。
思路
這道題一開始採用了貪心策略，但是並不可行，因為這個只能求出局部最小，並不能求出全局最小，所以不符合題意。
下面給出貪心程式碼：
class Solution(object): def minimumTotal(self, triangle): res = 0 row = len(triangle) t = 0 for i in range(row): if i==0: res+=triangle[0][0] else: t1,t2 = t,t+1 if triangle[i][t1]> triangle[i][t2]: t=t2 else: t=t1 res+=triangle[i][t] return res
假設當前行的坐標為(i,j)，那麼下一行相關的坐標為(i+1,j)與(i+1,j+1)，也就是求這個相關坐標對應點的最小值，然後依次往下計算，得出一個局部最小路徑，然後對比不同路徑得到全局最優的最小路徑，最後返回最小路徑和即可。
原： [ [-1], [2,3], [1,-1,-3] ] 求和： [ [-1+min(1,0)=-1], [2+min(1,-1)=1,3+min(-1,-3)=0], [1,-1,-3] ]
由此圖可知，自底向上計算，最終的第一個元素就是最後的最短路徑。
遞歸法
遞歸法，首先確定終止條件，我們知道遞歸一輪後，會回到起點，那麼當傳入坐標(0,0)時候，遞歸終止條件就是行數超過指定行。然後依次遞歸回去往上計算。
class Solution: def minimumTotal(self, triangle): if not triangle: return 0 return self._minimumTotal(0, 0, triangle) def _minimumTotal(self, row, col, triangle): if row>len(triangle)-1: return triangle[row][col] return triangle[row][col]+self._minimumTotal(row+1,col,triangle)+self._minimumTotal(row+1,col+1,triangle)
但是這樣做存在著大量的重複運算。我們可以通過記憶化搜索的方式來優化上面的問題。
記憶化搜索
class Solution: def minimumTotal(self, triangle): if not triangle: return 0 mem = [[0 for i in range(len(triangle[-1]))] for j in range(len(triangle))] return self._minimumTotal(0, 0, triangle,mem) def _minimumTotal(self, row, col, triangle,mem): if row + 1 == len(triangle): return triangle[row][col] if mem[row][col]: return mem[row][col] mem[row][col] = triangle[row][col] + min(self._minimumTotal(row + 1, col, triangle,mem), self._minimumTotal(row + 1, col + 1, triangle,mem)) return mem[row][col]
動態規劃
採用自底向上的動態規劃方法，其中dp數組表示每次從末尾到(i,j)這個位置的最小路徑和，到達頂端則為最終要求解的最短路徑和！
第一種：開闢二維數組空間
class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: row=len(triangle) col=len(triangle[-1]) dp=[[0 for i in range(col)] for j in range(row)] for i in range(row-1,-1,-1): for j in range(len(triangle[i])): if i==row-1: dp[i][j]=triangle[i][j] else: dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j] return dp[0][0]
第二種：開闢一維數組空間
class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: row=len(triangle) col=len(triangle[-1]) dp=[0 for i in range(row*col)] for i in range(row-1,-1,-1): for j in range(len(triangle[i])): if i==row-1: dp[i*col+j]=triangle[i][j] else: dp[i*col+j]=min(dp[(i+1)*col+j],dp[(i+1)*col+j+1])+triangle[i][j] return dp[0]
上述優化版：
考慮到dp二維數組中存放這的是從末尾到某一位置的最短路徑和，那麼噹噹前行操作完畢，此數據就可以通過在下一行做修改，也就是說利用這個特性，那麼就直接轉為一位數組即可解決，不斷修改某個重複修改。
class Solution(object): def minimumTotal(self, triangle): mini = triangle[-1] for row in range(len(triangle) - 2, -1, -1): for j in range(len(triangle[row])): mini[j] = min(mini[j], mini[j + 1]) + triangle[row][j] return mini[0]
第三種：原地修改
class Solution(object): def minimumTotal(self, triangle): for row in range(len(triangle) - 2, -1, -1): for j in range(len(triangle[row])): triangle[row][j] = min(triangle[row + 1][j], triangle[row + 1][j + 1]) + triangle[row][j] return triangle[0][0]
這個原地修改真的非常棒！一開始最後一行所有數據不變，我們就想要最後一行的原數據存儲到我們的dp數組中，後面我們就是不斷修改對應(i,j)的位置，因為是從底向上的，也就是每一行的每一列數據它只修改一次，所以直接使用原數組即可，空間複雜度達到了O(1)！
從上面兩道題我們又深入分析了動態規劃的學習，從遞推到記憶化，再到必殺動態規劃！
