福建省建设执业资格注册管理中心网站,空间网站打不开,郑州交通建设投资有限公司网站,学校网站建设市场分析对于动态规划问题#xff0c;将拆解为如下五步曲
确定dp数组#xff08;dp table#xff09;以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
509.斐波那契数
思路#xff1a; 确定dp数组#xff08;dp table#xff09;以及下标的含义#x…对于动态规划问题将拆解为如下五步曲
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
509.斐波那契数
思路 确定dp数组dp table以及下标的含义dp[i]的定义为第i个数的斐波那契数值是dp[i] 确定递推公式状态转移方程 dp[i] dp[i - 1] dp[i - 2] dp数组如何初始化dp[0] 0dp[1] 1 确定遍历顺序从前到后遍历 举例推导dp数组推导一下当N为10的时候dp数组应该是如下的数列 0 1 1 2 3 5 8 13 21 34 55
class Solution:def fib(self, n: int) - int:dp [0 for _ in range(n1)]if n 1:return 0dp[0] 0dp[1] 1for i in range(2,n1):dp[i] dp[i-1] dp[i-2]return dp[n]70.爬楼梯
思路 确定dp数组dp table以及下标的含义dp[i] 爬到第i层楼梯有dp[i]种方法 确定递推公式 dp[i] 可以有两个方向推出来。 首先是dp[i - 1]上i-1层楼梯有dp[i - 1]种方法那么再一步跳一个台阶不就是dp[i]了么。 还有就是dp[i - 2]上i-2层楼梯有dp[i - 2]种方法那么再一步跳两个台阶不就是dp[i]了么。 dp数组如何初始化dp[0] 1dp[1] 1 确定遍历顺序从前到后遍历 举例推导dp数组
class Solution:def climbStairs(self, n: int) - int:dp [0 for _ in range(n1)]if n 0:return 0dp[0] 1dp[1] 1for i in range(2,n1):dp[i] dp[i-1] dp[i-2]return dp[n]746.使用最小花费爬楼梯
思路 确定dp数组dp table以及下标的含义dp[i]爬到楼顶的花费 确定递推公式 dp[i - 1]到上i-1层楼梯花费dp[i - 1]i-1到i花费dp[i - 1]cost[i-1] dp[i - 2]上i-2层楼梯花费dp[i - 2]i-2到i花费dp[i - 2]cost[i-2] dp [i] min(dp[i - 1]cost[i-1]dp[i - 2]cost[i-2]) dp数组如何初始化dp[0] 0dp[1] 0 **注意**题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 从 到达 第 0 个台阶是不花费的但从 第0 个台阶 往上跳的话需要花费 cost[0]。 确定遍历顺序从前到后遍历 举例推导dp数组
cost [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 来模拟一下dp数组的状态变化如下 class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:n len(cost) dp [0 for _ in range(n1)]if n 1:return 0dp[0] 0dp[1] 0for i in range(2, n1):dp[i] min(dp[i-1]cost[i-1],dp[i-2]cost[i-2])return dp[n]
