哪个全球购网站做的好处,google建站,wordpress随机图片,主题森林wordpress代码随想录算法训练营第四十一天
509. 斐波那契数
题目链接#xff1a;509. 斐波那契数 动规五部曲#xff1a;
确定dp数组以及下标的含义#xff1a;第i个数的斐波那契数值是dp[i]确定递推公式#xff1a;dp[i] dp[i - 1] dp[i - 2];dp数组如何初始化#xff1a;dp[…代码随想录算法训练营第四十一天
509. 斐波那契数
题目链接509. 斐波那契数 动规五部曲
确定dp数组以及下标的含义第i个数的斐波那契数值是dp[i]确定递推公式dp[i] dp[i - 1] dp[i - 2];dp数组如何初始化dp[0] 0;dp[1] 1;确定遍历顺序从前向后遍历打印dp数组。
class Solution {
public:int fib(int n) {vectorint dp(n1);//创建dp数组if(n1)return n;//处理特殊条件dp[0] 0;//初始化dp数组dp[1] 1;for(int i 2;in;i){dp[i]dp[i-1]dp[i-2];//递推公式更新结果coutdp[i]endl;//打印dp数组}return dp[n];}
};70. 爬楼梯
题目链接70. 爬楼梯
确定dp数组以及下标的含义达到i级台阶有dp[i]种方法确定递推公式dp[i] dp[i - 1] dp[i - 2];dp数组如何初始化dp[0] 0;dp[1] 1;dp[2] 2;确定遍历顺序从前向后遍历打印dp数组。
class Solution {
public:int climbStairs(int n) {vectorint dp(n 3);dp[0] 0;dp[1] 1;dp[2] 2;for (int i 3; i n; i) {dp[i] dp[i - 1] dp[i - 2];coutdp[i]endl;//打印dp数组}return dp[n];}
};746. 使用最小花费爬楼梯
题目链接746. 使用最小花费爬楼梯
确定dp数组以及下标的含义达到i级台阶花费的最小总体力dp[i]确定递推公式一次跳跃可以跳1个台阶或者2个台阶所以dp[i]总花费可以是dp[i-1]总花费cost[i-1]从i-1处向上跳的花费或者dp[i-2]总花费cost[i-2]从i-2处向上跳的花费。这两个值其中较小的一个。dp数组如何初始化到达0和1位都可以不用花费。dp[0] 0;dp[1] 0;确定遍历顺序从前向后遍历打印dp数组。
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int n cost.size();vectorint dp(n2);dp[0] 0;dp[1] 0;for(int i 2;in;i){dp[i] min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);coutdp[i]endl;//打印dp数组}return dp[n];}
};
