社区类网站建设,舆情报告模板,建设网站网站多少钱,网站开发常见面试理论基础 代码随想录 视频#xff1a;从此再也不怕动态规划了#xff0c;动态规划解题方法论大曝光 #xff01;| 理论基础 |力扣刷题总结| 动态规划入门_哔哩哔哩_bilibili 动态规划#xff1a;如果某一问题有很多重叠子问题#xff0c;使用动态规划是最有效的。所以动态…理论基础 代码随想录 视频从此再也不怕动态规划了动态规划解题方法论大曝光 | 理论基础 |力扣刷题总结| 动态规划入门_哔哩哔哩_bilibili 动态规划如果某一问题有很多重叠子问题使用动态规划是最有效的。所以动态规划中每一个状态一定是由上一个状态推导出来的这一点就区分于贪心贪心没有状态推导而是从局部直接选最优的
对于动态规划问题要搞清楚以下几点
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组 509. 斐波那契数 代码随想录 视频手把手带你入门动态规划 | LeetCode509.斐波那契数_哔哩哔哩_bilibili 动态规划五部曲
1.确定dp[i]的含义第i个数的斐波那契数值为dp[i]
2.确定递推公式dp[i] dp[i-1]dp[i-2]
3.dp数组如何初始化dp[0]0,dp[1]1
4.遍历顺序从递归公式dp[i] dp[i - 1] dp[i - 2];中可以看出dp[i]是依赖 dp[i - 1] 和 dp[i - 2]那么遍历的顺序一定是从前到后遍历的
5.举例推导dp数组
按照这个递推公式dp[i] dp[i - 1] dp[i - 2]我们来推导一下当N为10的时候dp数组应该是如下的数列
0 1 1 2 3 5 8 13 21 34 55
如果代码写出来发现结果不对就把dp数组打印出来看看和我们推导的数列是不是一致的。
class Solution:def fib(self, n: int) - int:if n 2:return 0dp [0]* (n1)dp[0]0dp[1]1for i in range(2,n1):dp[i] dp[i-1] dp[i-2]return dp[n]也可以只维护两个数值 class Solution:def fib(self, n: int) - int:if n 1:return ndp [0, 1]for i in range(2, n 1):total dp[0] dp[1]dp[0] dp[1]dp[1] totalreturn dp[1] 递归法
class Solution:def fib(self, n: int) - int:if n 0:return 0if n 1:return 1return self.fib(n-1)self.fib(n-2) 70. 爬楼梯 代码随想录 视频带你学透动态规划-爬楼梯对应力扣70.爬楼梯| 动态规划经典入门题目_哔哩哔哩_bilibili 到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来那么就可以想到动态规划
1.确定dp[i]的含义爬到第i层楼梯有dp[i]种方法
2.确定递推公式dp[i] dp[i-1]dp[i-2]
3.dp数组如何初始化dp[1]1,dp[2]2
4.遍历顺序从递归公式dp[i] dp[i - 1] dp[i - 2];中可以看出dp[i]是依赖 dp[i - 1] 和 dp[i - 2]那么遍历的顺序一定是从前到后遍历的
5.举例推导dp数组
class Solution:def climbStairs(self, n: int) - int:dp [0]*(n1)dp[1] 1dp[2] 2for i in range(3,n1):dp[i] dp[i-1] dp[i-2]return dp[n] 746. 使用最小花费爬楼梯 代码随想录 视频讲解动态规划开更了| LeetCode746. 使用最小花费爬楼梯_哔哩哔哩_bilibili 1.确定dp[i]的含义爬到第i层楼梯有dp[i]种方法
2.确定递推公式dp[i] min(dp[i-1]cost[i-1],dp[i-2]cost[i-2])
3.dp数组如何初始化dp[0]0,dp[1]0
4.遍历顺序从递归公式dp[i] dp[i - 1] dp[i - 2];中可以看出dp[i]是依赖 dp[i - 1] 和 dp[i - 2]那么遍历的顺序一定是从前到后遍历的
5.举例推导dp数组
class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:dp [0]*(len(cost)1)dp[0] 0dp[1] 0for 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)]
