淘宝的网站建设的目标,风险的网站怎么出现,免费的网页设计成品详解,底价网站建设day38打卡
509. 斐波那契数
状态表示#xff1a;
第i个数的斐波那契数是dp[i]
状态转移方程
见题目#xff1a;dp[i] dp[i-1] dp[i-2]
初始化
见题目#xff0c;dp[0] 0#xff0c;dp[1] 1#xff0c;本题用两个变量代替即可。
填表顺序
从左到右…day38打卡
509. 斐波那契数
状态表示
第i个数的斐波那契数是dp[i]
状态转移方程
见题目dp[i] dp[i-1] dp[i-2]
初始化
见题目dp[0] 0dp[1] 1本题用两个变量代替即可。
填表顺序
从左到右
返回值
dp[i]
class Solution {
public:int fib(int n) {if(n 1) return n;int a 0, b 1;int ret 0;for(int i 2; i n; i){ret a b;a b;b ret;}return ret;}
};70. 爬楼梯
状态表示
爬到第i层一共用dp[i]种方法
状态转移方程
到达第i层前一级可以是i-1也可以是i-2(题目提到可以走1或者2步)参照之前的状态表示
所以dp[i] dp[i-1] dp[i-2]
初始化
dp[1] 1dp[2] 2
填表顺序
从左到右
返回值
dp[n]
class Solution {
public:int climbStairs(int n) {if(n 1) return n;//创建dp表vectorint dp(n1, 0);//初始化dp[1] 1, dp[2] 2;//填表for(int i 3; i n; i){dp[i] dp[i-1] dp[i-2];}//返回值return dp[n];}
};746. 使用最小花费爬楼梯
状态表示
爬到第i层最少需要花dp[i]的钱
状态转移方程
第i层的前一级是i-1层或者是i-2层选择一个花费少的即可(即为之前的花费当前层的花费)
dp[i] min(dp[i-1] cost[i-1], dp[i-2] cost[i-2])
初始化
无特殊处理
填表顺序
从左到右
返回值
dp[n]
class Solution {
public:int minCostClimbingStairs(vectorint cost) {//创建dp数组int n cost.size();vectorint dp(n1);//初始化//填表for(int i 2; i n; i){dp[i] min(dp[i-1] cost[i-1], dp[i-2] cost[i-2]);}return dp[n];}
};如果有空间复杂度要求把dp[i-1]和dp[i-2]换为两个变量即可。
