动态规划步步为营之[递推]->[记忆化]->[动态规划]
- 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)！
从上面两道题我们又深入分析了动态规划的学习，从递推到记忆化，再到必杀动态规划！
