洛阳网络营销推广,长沙seo网站排名优化,建设景区网站推文,北京培训机构动态规划之使用最小花费爬楼梯 LCR 088. 使用最小花费爬楼梯解法1解法2 LCR 088. 使用最小花费爬楼梯
LCR 088. 使用最小花费爬楼梯 解法1
状态表示#xff08;这是最重要的#xff09;#xff1a;dp[i]表示以第i级台阶为楼层顶部#xff0c;到达第i层台阶的最低花费。 状… 动态规划之使用最小花费爬楼梯 LCR 088. 使用最小花费爬楼梯解法1解法2 LCR 088. 使用最小花费爬楼梯
LCR 088. 使用最小花费爬楼梯 解法1
状态表示这是最重要的dp[i]表示以第i级台阶为楼层顶部到达第i层台阶的最低花费。 状态转移方程最难的dp[i] min(dp[i-1]cost[i-1], dp[i-2]cost[i-2]); 初始化根据题意我们需要知道到达第1层和第2层台阶的最低花费第1层和第2层台阶的最低花费为0并且vector会自动将所有元素初始化为0所以可以忽略这一步。 填表顺序当我们求解当前问题时需要知道所需较小子问题的解这就需要我们先求解得到较小子问题的解这就是填表顺序。我们这道解法是从左向右填表。 返回值n cost.size(); return dp[n];
代码实现
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int n cost.size();vectorint dp(n1);int i 0;for(i 2; i n; i){dp[i] min(dp[i-1]cost[i-1], dp[i-2]cost[i-2]);}return dp[n];}
};解法2
状态表示这是最重要的dp[i]表示从第i级台阶开始到达楼层顶部的最低花费。 状态转移方程最难的dp[i] cost[i]min(dp[i1], dp[i2]); 初始化n cost.size(); dp[n-1]cost[n-1], dp[n-2]cost[n-2]; 填表顺序当我们求解当前问题时需要知道所需较小子问题的解这就需要我们先求解得到较小子问题的解这就是填表顺序。我们这道解法是从右向左填表。 返回值return min(dp[0], dp[1]);
代码实现
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int n cost.size();vectorint dp(n);dp[n-1]cost[n-1], dp[n-2]cost[n-2];for(int i n-3; i 0; i--){dp[i] cost[i]min(dp[i1], dp[i2]);}return min(dp[0], dp[1]);}
};创作不易你的点赞和关注都是对我莫大的鼓励再次感谢您的观看
