福州企业网站,网站开发预算报价表,机械公司网站建设,唐山app开发公司509. 斐波那契数
五部曲#xff1a;
dp数组下标及含义#xff1a;dp[i]表示第i个斐波那契数的值dp数组初始化#xff1a;dp[0]0#xff0c;dp[1]1递推公式#xff1a;dp[i] dp[i - 1] dp[i - 2]遍历方向#xff1a;从前往后dp数组推到举例#xff1a;0#xff0c;1…509. 斐波那契数
五部曲
dp数组下标及含义dp[i]表示第i个斐波那契数的值dp数组初始化dp[0]0dp[1]1递推公式dp[i] dp[i - 1] dp[i - 2]遍历方向从前往后dp数组推到举例011235813
class Solution {
public:int fib(int n) {if(n1) return n;vectorint dp(n1);dp[0] 0;dp[1] 1;for(int i 2;in;i){dp[i] dp[i-1] dp[i-2];}return dp[n];}
};70. 爬楼梯
五部曲
dp数组下标及含义dp[i]表示第i层楼梯有几种方法dp数组初始化dp[1]1dp[2]2递推公式dp[i] dp[i - 1] dp[i - 2]遍历方向从前往后dp数组推到举例011235813
我们可以看出本题其实就是斐波那契数列问题。
class Solution {
public:int climbStairs(int n) {if (n 1) return n; vectorint dp(n 1);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. 使用最小花费爬楼梯
五部曲
dp数组下标及含义dp[i]表示到达第i层楼梯最小花费dp数组初始化dp[0]0dp[1]1递推公式dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2])遍历方向从前往后dp数组推到举例以cost [1,100,1,1,1,100,1,1,100,1]为例 00122334456
class Solution {
public:int minCostClimbingStairs(vectorint cost) {vectorint dp(cost.size() 1);dp[0] 0;dp[1] 0;for(int i2;icost.size();i){dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);}return dp[cost.size()];}
};
