吉安哪家做网站的公司好,视频网站程序模板,关于开展网站建设工作的通知,网站的设计需要什么动态规划#xff0c;如果某一问题有很多重叠子问题#xff0c;使用动态规划是最有效的。动态规划中每一个状态一定是由上一个状态推导出来的#xff0c;这一点就区分于贪心#xff0c;贪心没有状态推导#xff0c;而是从局部直接选最优的。
动态规划问题五步曲
确定dp数…动态规划如果某一问题有很多重叠子问题使用动态规划是最有效的。动态规划中每一个状态一定是由上一个状态推导出来的这一点就区分于贪心贪心没有状态推导而是从局部直接选最优的。
动态规划问题五步曲
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
509. 斐波那契数
dp数组以及下标的含义dp[i]代表数字i的斐波那契数递推公式dp[i] dp[i-1] dp[i-2]dp数组初始化dp[0] 0 dp[1] 1遍历顺序从前往后遍历举例推导dp数组0 1 1 2 3 5 8 13 21
class Solution:def fib(self, n: int) - int:if n 1:return ndp [0] * (n1)dp[0] 0dp[1] 1for i in range(2, n1):dp[i] dp[i-1] dp[i-2]return dp[n]
因为在dp的递推公式中只使用了前两个数值所以可以不用声明数组只要保留前两个值即可
class Solution:def fib(self, n: int) - int:if n 1:return npre1 0pre2 1for i in range(2, n1):sum pre1 pre2pre1 pre2pre2 sumreturn pre2
70. 爬楼梯
第n阶楼梯可以由 n-1阶楼梯爬1步上去 和 n-2阶楼梯爬2步上去
dp数组以及下标的含义dp[i]代表第i阶楼梯有多少种方法爬上去递推公式dp[i] dp[i-1] dp[i-2]dp数组初始化dp[1] 1 dp[2] 2本题n1dp[0]没有意义遍历顺序从前往后遍历举例推导dp数组从1开始 1 2 3 5 8 13
class Solution:def climbStairs(self, n: int) - int:if n 1:return ndp [0] * (n1)dp[1] 1dp[2] 2for i in range(3, n1):dp[i] dp[i-1] dp[i-2]return dp[n]
注上面的代码也可以将数组优化为使用前两个数值
746. 使用最小花费爬楼梯
第n阶楼梯可以由 n-1阶楼梯爬1步上去 和 n-2阶楼梯爬2步上去
dp数组以及下标的含义dp[i]代表爬上第i阶楼梯需要多少花费递推公式dp[i] min(dp[i-1]cost[i-1], dp[i-2]cost[i-2])dp数组初始化dp[0] 0 dp[1] 0遍历顺序从前往后遍历举例推导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[-1]
