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