网站建设策划书范文提纲,达州网站开发qinsanw,太仓公司网站建设电话,嵌入式开发工程师贴一下动态规划的步骤#xff08;5步#xff09;#xff0c;就像是之前递归一样#xff0c;需要每次落实到位。
确定dp数组#xff08;dp table#xff09;以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组 509. 斐波那契
注意到n的范… 贴一下动态规划的步骤5步就像是之前递归一样需要每次落实到位。
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组 509. 斐波那契
注意到n的范围是30以内一个更快的方法是直接把这个数组先算出来然后直接取。
class Solution(object):def fib(self, n)::type n: int:rtype: intfib_list self.pre_print()return fib_list[n]def pre_print(self):fib_list [0, 1, 1]for i in range(3, 31):fib_list.append(fib_list[i-2] fib_list[i-1])return fib_list
当然可以使用递归
class Solution(object):def fib(self, n)::type n: int:rtype: int## 递归解法if n 2:return nelse:return self.fib(n-1) self.fib(n-2) 70. 爬楼梯
在规定了每次只能走1或者2步的时候本题的本质就是求解斐波那契鹅数列。 可以看到dp[i]在第三位开始往前看一位dp[i-1]只有一种情况就是走1步往前看两位dp[i-2]只有一种情况就是走2步因为走1步的已经算在dp[i-1]里面了
所以dp[i]dp[i-1]dp[i-2]
则自然可以看出是斐波那契。
关于dp[0]的初始化由于题目说是从1开始所以0直接排除了。但是对于一般的动态规划为题如之前的斐波那契都需要考虑0的初始化。本题直接初始化dp[1]1,dp[2]2即可。
class Solution(object):def climbStairs(self, n)::type n: int:rtype: intif n 2:return n# 初始化dp [0] * 3dp[1] 1dp[2] 2 # 实际上只用到了2个位置# 推倒关系for i in range(3, n1): # 注意i开始和结束的值total dp[1] dp[2]dp[1] dp[2]dp[2] totalreturn dp[2]
746. 使用最小花费爬楼梯
本题关键在于如何确定dp数组和下标的含义。
1、确定dp数组和下标的含义数组的第i个代表走到第i个所需要的最小花费
2、初始化由于0和1不需要花费所以dp都是0
3、递推当前i个的最小花费是取决于前2个dp值和cost的值取和的最小值。
class Solution(object):def minCostClimbingStairs(self, cost)::type cost: List[int]:rtype: intdp [0] * (len(cost)1)dp[0], dp[1] 0, 0for i in range(2, len(dp)):dp[i] min(dp[i-1] cost[i-1], dp[i-2] cost[i-2])return dp[-1]
Day38完结
