动态规划之使用最小花费爬楼梯【LeetCode】

简介: 动态规划之使用最小花费爬楼梯【LeetCode】


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(vector<int>& cost) {
        int n= cost.size();
        vector<int> dp(n+1);
        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[i+1], dp[i+2]);

初始化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(vector<int>& cost) {
        int n = cost.size();
        vector<int> 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[i+1], dp[i+2]);
        }
        return min(dp[0], dp[1]);
    }
};

     😄 创作不易,你的点赞和关注都是对我莫大的鼓励,再次感谢您的观看😄

相关文章
|
6天前
|
机器学习/深度学习 存储 算法
LeetCode 题目 95:从递归到动态规划实现 不同的二叉搜索树 II
LeetCode 题目 95:从递归到动态规划实现 不同的二叉搜索树 II
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(4)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
|
3天前
|
存储 算法
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(1)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
|
6天前
|
存储 算法 数据挖掘
力扣174题动态规划:地下城游戏(含模拟面试)
力扣174题动态规划:地下城游戏(含模拟面试)
|
6天前
|
存储 算法 数据可视化
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
|
6天前
|
存储 算法 数据可视化
LeetCode 132题详解:使用动态规划与中心扩展法解决分割回文串 II 的最少分割次数问题
LeetCode 132题详解:使用动态规划与中心扩展法解决分割回文串 II 的最少分割次数问题
|
6天前
|
存储 算法 数据可视化
LeetCode 131题详解:高效分割回文串的递归与动态规划方法
LeetCode 131题详解:高效分割回文串的递归与动态规划方法
|
6天前
|
存储 算法 数据可视化
LeetCode 题目 96:从动态规划、递归到卡塔兰数实现不同的二叉搜索树
LeetCode 题目 96:从动态规划、递归到卡塔兰数实现不同的二叉搜索树
|
6天前
|
存储 算法 数据可视化
LeetCode 题目 97:动态规划、递归到广度优先搜索BFS 实现交错字符串
LeetCode 题目 97:动态规划、递归到广度优先搜索BFS 实现交错字符串
|
6天前
|
存储 SQL 算法
优化解码方法:记忆化搜索和空间优化动态规划的实用指南 【LeetCode 题目 91】
优化解码方法:记忆化搜索和空间优化动态规划的实用指南 【LeetCode 题目 91】