html网站如何更新,wordpress 4.7 多站点,无锡网页建站公司,北京网站建设文章理论基础
题型
动归基础#xff08;这一节就是基础题#xff09;背包问题打家劫舍股票问题子序列问题
动态规划五部曲
确定dp数组及其下标的含义确定递推公式dp数组如何初始化遍历顺序打印dp数组
509. 斐波那契数
简单~
dp数组及下标含义#xff1a; dp[i]表示第i各斐…理论基础
题型
动归基础这一节就是基础题背包问题打家劫舍股票问题子序列问题
动态规划五部曲
确定dp数组及其下标的含义确定递推公式dp数组如何初始化遍历顺序打印dp数组
509. 斐波那契数
简单~
dp数组及下标含义 dp[i]表示第i各斐波那契数值为dp[i]递推公式dp[i] dp[i-1] -dp[i-2]dp数组如何初始化dp[0] 0; dp[1] 1;题目描述中有敌意遍历顺序从前往后打印dp数组
当前位置的值只与该位置的前两个数值有关只需要维护长度为2的数组。
class Solution {
public:int fib(int n) {if(n0 || n1) return n;vectorint dp(2);dp[0] 0; dp[1] 1;for(int i2; in; i){int sum dp[1] dp[0];dp[0] dp[1];dp[1] sum;}return dp[1];}
};class Solution {public int fib(int n) {if(n 0 || n 1) return n;int[] dp new int[2];dp[0] 0; dp[1] 1;for(int i 2; in; i){int sum dp[0] dp[1];dp[0] dp[1];dp[1] sum;}return dp[1];}
}class Solution(object):def fib(self, n)::type n: int:rtype: intif n 0 or n 1:return ndp [0,1]for i in range(2, n1):sum_ dp[0] dp[1]dp[0] dp[1]dp[1] sum_return dp[1] 参考文章
https://programmercarl.com/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
70. 爬楼梯
要明白如果爬n层有两种情况 一种是从n-2层迈两步上来的一种是从n-1层迈一步上来的。所以到达第n层的方法数量到达第n-2层的方法数到达第n-1层的方法数。
dp数组及其下标含义 dp[i] 表示到达第i层的方法数量递推公式 dp[i] dp[i-1] dp[i-2]dp数组初始化 dp[1] 1 dp[2] 20没有实际意义遍历顺序从前往后打印dp数组
当前位置数值只与当前位置前2个位置数值有关只需要维护长度为2的数组但是0没有实际意义为了实现更加明确的初始化我们定义长度为3的数组0这个位置不进行初始化。
class Solution {
public:int climbStairs(int n) {if(n1 || n2) return n;vectorint dp(3);dp[1] 1;//空出0来因为没有意义dp[2] 2;for(int i 3; i n; i){int sum dp[1] dp[2];dp[1] dp[2];dp[2] sum;}return dp[2];}
};class Solution {public int climbStairs(int n) {if(n 1 || n 2) return n;int[] dp new int[3];dp[1] 1; dp[2] 2;for(int i 3; i n; i){int sum dp[1] dp[2];dp[1] dp[2];dp[2] sum;}return dp[2];}
}class Solution(object):def climbStairs(self, n)::type n: int:rtype: intif n 1 or n 2:return ndp [None, 1, 2]for i in range(3, n1):sum_ dp[1] dp[2]dp[1] dp[2]dp[2] sum_return dp[2]参考文章
https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
746. 使用最小花费爬楼梯
Note注意题目描述该位置不花费体力往上跳花费体力。并且cost的长度是顶楼。
dp数组及其下标含义dp[i] 到达第i层所需要的最小花费为dp[i]递推公式 dp[i] min(dp[i-1] cost[i-1], dp[i-2] cost[i-2]);dp数组如何初始化 dp[0]0;dp[1]0;//因为当前位置不花费向上跳才花费所以都初始化为0遍历顺序从前往后打印dp数组
class Solution {
public:int minCostClimbingStairs(vectorint cost) {if(cost.size()2) return 0;vectorint dp(2);for(int i 2; i cost.size(); i){int minCost min(dp[0] cost[i-2], dp[1] cost[i-1]);dp[0] dp[1];dp[1] minCost;}return dp[1];}
};class Solution {public int minCostClimbingStairs(int[] cost) {if(cost.length2) return 0;int[] dp new int[]{0, 0};for(int i 2; i cost.length; i){int minCost Math.min(dp[0] cost[i-2], dp[1] cost[i-1]);dp[0] dp[1];dp[1] minCost;}return dp[1];}
}class Solution(object):def minCostClimbingStairs(self, cost)::type cost: List[int]:rtype: intif len(cost)2:return 0dp [0, 0]for i in range(2, len(cost)1):minCost min(dp[0]cost[i-2], dp[1]cost[i-1])dp[0] dp[1]dp[1] minCostreturn dp[1]参考文章
https://programmercarl.com/0746.%E4%BD%BF%E7%94%A8%E6%9C%80%E5%B0%8F%E8%8A%B1%E8%B4%B9%E7%88%AC%E6%A5%BC%E6%A2%AF.html
