今日步步为营,实战dp,采用递推、记忆化、动态规划,三种方法解决两道题目,并深入研究动态规划套路。
今日题目
题目描述
假设你正在爬楼梯。需要 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],
[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)!
从上面两道题我们又深入分析了动态规划的学习,从递推到记忆化,再到必杀动态规划!