绍兴企业建站模板,自考软件开发工具,php网页模板,wordpress系统安装目录 动规五部曲LeetCode 509. 斐波那契数LeetCode 70. 爬楼梯LeetCode 746. 使用最小花费爬楼梯 动规五部曲
确定dp数组以及下标的含义确定递归公式dp数组如何初始化确定遍历顺序举例推导dp数组
LeetCode 509. 斐波那契数
力扣题目链接
本题最直观是用递归方法
class Sol… 目录 动规五部曲LeetCode 509. 斐波那契数LeetCode 70. 爬楼梯LeetCode 746. 使用最小花费爬楼梯 动规五部曲
确定dp数组以及下标的含义确定递归公式dp数组如何初始化确定遍历顺序举例推导dp数组
LeetCode 509. 斐波那契数
力扣题目链接
本题最直观是用递归方法
class Solution:def fib(self, n: int) - int:if n 0: return 0elif n 1: return 1else:return self.fib(n-1) self.fib(n-2)当然本题也可以用动态规划是最简单的问题
class Solution:def fib(self, n: int) - int:dp [0] * (n1)if n 0:dp[1] 1for i in range(2, n1):dp[i] dp[i-1] dp[i-2]return dp[-1]LeetCode 70. 爬楼梯
力扣题目链接 本题代码实际跟上一题斐波那契数一样。 如果是1个台阶只有一种方法如果有两个台阶也只有两种方法这就是动规的初始值。 当n2时到达第n个台阶的最后一步可以爬1个台阶也可以爬2个台阶如果爬1个台阶那么前面的种数就跟n-1个台阶的情况一样如果爬2个台阶那么跟n-2个台阶的情况一样。 所以n个台阶的方法n-1个台阶的方法数n-2个台阶的方法数。这不就是不同初始值的斐波那契数列吗
class Solution:def climbStairs(self, n: int) - int:if n 2:return ndp [0] * ndp[0] 1dp[1] 2for i in range(2, n):dp[i] dp[i-1] dp[i-2]return dp[-1]LeetCode 746. 使用最小花费爬楼梯
力扣题目链接
确定dp数组以及下标的含义到达第i个台阶的最小花费确定递归公式dp[i] min(dp[i-1]cost[i-1], dp[i-2]cost[i-2])dp数组如何初始化可以从下标为 0 或下标为 1 的台阶开始爬楼梯意味着dp[0], dp[1]初始值都为0确定遍历顺序从前向后遍历举例推导dp数组
class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:dp [0] * (len(cost) 1)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[-1]今日毕
