DP问题类型:
动态规划比较重要的是找到前后两个状态之间的联系,在向后遍历的过程中注意遍历的顺序和初始化操作。
动归基础类问题
背包问题
打家劫舍
股票问题
子序列问题
DP问题的一些注意事项:
动态规划类的问题代码都是比较简洁的,按照dp打印逻辑观察打印出来的数值。
- dp数组以及下标的含义dp[i][j],dp[i]
- 递推公式
- dp数组的初始化,有时候初始化成1,有时候初始化成0,有时候从某个下标开始初始化成1
- 遍历顺序:两层for循环的顺序是怎样的
- 打印dp数组:纠正动态规划的问题
509. 斐波那契数
复习动归五部曲:
dp数组-初始化-递推公式-遍历顺序-打印dp数组
入门级别的问题
class Solution:
def fib(self, n: int) -> int:
# 递归解法
def r(n):
if n == 0 : return 0
if n == 1 : return 1
return r(n-1) + r(n-2)
return r(n)
'''
# 动态规划方法
dp = [0] * (n+1)
if n == 0 : return 0
if n == 1 : return 1
dp[0] = 0
dp[1] = 1
for i in range(2,n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[-1]
'''
''' # 一般方法
if n == 0: return 0
if n == 1: return 1
cur = 1
pre = 0
i = 2
while i<=n:
temp = cur
cur = pre + cur
pre = temp
i += 1
return cur
'''
70. 爬楼梯
核心思路: 第i个台阶收到前1个台阶和倒数第二个台阶影响
问题的思考方式是先那几个进行举例,然后找到其中的规律。三阶可以用一阶和二阶楼梯进行推导。
dp五部曲进行思考:文章来源:https://www.toymoban.com/news/detail-466425.html
- 确定dp[i]含义:第i个台阶的上楼的种类
- 递推公式:dp[i] = dp[i-1] + dp[i-2]
- 数组的初始化:dp[0] = 0 dp[1] = 1
- 遍历方式:从前往后
- 打印dp数组
class Solution:
def climbStairs(self, n: int) -> int:
# 当前楼梯走几步受到之前两个台阶的影响。
# 根据dp五部曲进行求解
dp = [0] * (n+1)
if n == 0: return 0
if n == 1: return 1
dp[0] = 1
dp[1] = 1
for i in range(2,n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
746. 使用最小花费爬楼梯
有两个数组cost[i],当前台阶的花费受到前两个台阶花费的影响。
dp五步曲进行思考:文章来源地址https://www.toymoban.com/news/detail-466425.html
- dp[i]含义:第i个台阶的最小花费
- 递推公式:dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
- dp数组的初始化:dp[0] = 0,dp[1] = 0
- 遍历方式:从前往后
- 打印dp数组
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
dp = [0]*(len(cost)+1)
if len(cost) <=1 : return 0
dp[0] = 0
dp[1] = 0
for i in range(2,len(cost)+1):
dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
return dp[len(cost)]
到了这里,关于day38|动态规划-爬楼梯问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!