网站界面设计尺寸,网站域名登陆地址,杭州人才招聘网,软件开发网站开发动态规划理论基础动态规划#xff0c;英文#xff1a;Dynamic Programming#xff0c;简称DP#xff0c;如果某一问题有很多重叠子问题#xff0c;使用动态规划是最有效的。所以动态规划中每一个状态一定是由上一个状态推导出来的#xff0c;这一点就区分于贪心#xff…动态规划理论基础动态规划英文Dynamic Programming简称DP如果某一问题有很多重叠子问题使用动态规划是最有效的。所以动态规划中每一个状态一定是由上一个状态推导出来的这一点就区分于贪心贪心没有状态推导而是从局部直接选最优的。动态规划五部曲 确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组Dubug找问题的最好方式就是把dp数组打印出来看看究竟是不是按照自己思路推导的做动规的题目写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍心中有数确定最后推出的是想要的结果。 然后再写代码如果代码没通过就打印dp数组看看是不是和自己预先推导的哪里不一样。 如果打印出来和自己预先模拟推导是一样的那么就是自己的递归公式、初始化或者遍历顺序有问题了。 如果和自己预先模拟推导的不一样那么就是代码实现细节有问题。
LeetCode 509. 斐波那契数思路动态规划五部曲1. 确定dp数组dp table以及下标的含义。一个数组下标表示序列从哪里开始。2. 确定递推公式F(n) F(n-1) F(n-2)3. dp数组如何初始化下标0和下标1需要进行默认初始化后续下标为n的元素需要通过下标为n-1和n-2的元素相加得到。dp数组长度等于n1。4. 确定遍历顺序遍历顺序下标从小到大进行遍历。5. 举例推导dp数组print递推后dp数组Code
class Solution(object):def fib(self, n)::type n: int:rtype: intdp [0] * (n1) ## dp数组的初始化且确保总能获取到F(n)F(n)的最小数组长度为n1if n 1:dp[1] 1if n 0: ## 特殊情况处理return 0elif n 1:return 1length len(dp)for i in range(2,length): ### 左闭右开遍历顺序dp[i] dp[i-1] dp[i-2] ### 遍历公式 dubug查看dp数组return dp[n]LeetCode 70. 爬楼梯思路回溯算法也可以解决但会存在超时的问题。Code如下
class Solution(object):def climbStairs(self, n)::type n: int:rtype: intself.path []self.total 0self.sum 0nums [1, 2]self.backtracking(nums, n, 0)return self.sumdef backtracking(self, num, n, start_index):if self.total n:self.sum 1return if self.total n:return for i in range(start_index, len(num)):self.path.append(num[i])# print(self.path, self.path)self.total num[i]# print(self.total, self.total)self.backtracking(num, n, 0)self.total - num[i]self.path.pop()这道题的题目关键不是在于排序组合的获取即你走到这阶台阶的过程而是在于迈向更高台阶方法数目和低台阶方法数目的联系。台阶方法数目1阶1种方法( [1] )2阶2种方法( [1,1], [2] )3阶3种方法( [1,1,1], [1,2], [2,1])4阶5种方法( [1,1,1,1], [1,2,1], [2,1,1], [1,1,2], [2,2])......从上述方法数目我可以看得出到第N阶的方法总数F(N)其实就是F(N-1)F(N-2) —— 递归公式。为什么会有这种规律。因为迈的步子只为1和2因此如果你迈的步子为2那么从F(N-2)迈向F(N)可以通过只迈2步实现因此F(N)的方法总数中包含了F(N-2)。另外如果你迈的步子为1那从F(N-1)迈向F(N)可以通过只迈一步实现可以F(N)的方法总数中包含了F(N-1)这就是为什么是F(N) F(N-1) F(N-2)。递归五部曲1. 确定dp数组dp table以及下标的含义。下标为0表示迈1阶。因此迈的阶数 下标 1。2. 确定递推公式F(N) F(N-1) F(N-2)3. dp数组如何初始化因为后续相加是涉及到N-1和N-2因此前两个元素需要手动初始化。dp数组的长度 阶数n。4. 确定遍历顺序从前向后遍历更新dp数组。5. 举例推导dp数组print递推后dp数组Code
class Solution(object):def climbStairs(self, n)::type n: int:rtype: intdp [0] * nif n 1:return 1if n 1:dp[0] 1 ## 迈向第一级台阶的方法数目dp[1] 2 ## 迈向第二级台阶的方法数目length len(dp)for i in range(2,length):dp[i] dp[i-1] dp[i-2]return dp[n-1]其实递推公式和遍历顺序跟斐波那契数是一样的只不过在数组长度初始化和前两个值的初始化上有区别。LeetCode 746. 使用最小花费爬楼梯容易陷入贪心的思路即每次只与前面的元素的判断通过大小来选择局部最优。如下所示[1,100,1000,200]。如果贪心思路的话你前两个元素就会选择1指针右移一位后续选择100指针右移后续选择200这样的话总cost 301但实际上从100可以直接到200总cost 300。动规五部曲1. 确定dp数组dp table以及下标的含义。dp[i]表示跳到第 i 个台阶时需要花费的cost。2. 确定递推公式dp[i] min( dp[i-1] cost[i-1], dp[i-2] cost[i-2])即判断表示从第i-1个台阶出发跳1个台阶的花费和从i-2个台阶出发跳2个台阶的花费。第i-1个台阶和第i-2个台阶已经分别包含了之前跳到当前这个台阶的花费。3. dp数组如何初始化是跳的这个操作才需要花费因此当处于第1个台阶和第2个台阶时此时花费为0。因此dp[0] dp[1] 04. 确定遍历顺序从前向后遍历更新dp数组。5. 举例推导dp数组print递推后dp数组Code
class Solution(object):def minCostClimbingStairs(self, cost)::type cost: List[int]:rtype: int### 到达超出数组长度的下标就是到达楼梯顶部了。length len(cost)dp [0] * lengthif length 2:for i in range(2, length):dp[i] min(dp[i-1]cost[i-1], dp[i-2]cost[i-2])### 距离楼梯顶部差一个台阶 / 两个台阶时需要进行比较 one_step_cost dp[length-1] cost[length-1]two_step_cost dp[length-2] cost[length-2]if one_step_cost two_step_cost:return two_step_costelse:return one_step_cost
