广州网站开发小程序,山西建站,成都网站建设前50强,室内设计学校全国排名1. 题目解析
题目链接#xff1a;746. 使用最小花费爬楼梯 这个问题的理解其实相当简单#xff0c;只需看一下示例#xff0c;基本就能明白其含义了。
2.算法原理
一、设定状态表
为了解决这个问题#xff0c;我们首先要明确一个“状态表”。这个状态表其实就是一个记录…1. 题目解析
题目链接746. 使用最小花费爬楼梯 这个问题的理解其实相当简单只需看一下示例基本就能明白其含义了。
2.算法原理
一、设定状态表
为了解决这个问题我们首先要明确一个“状态表”。这个状态表其实就是一个记录表用来记录到达每一层楼时的最小花费。
我们设定dp[i]为到达第i层楼时的最小花费。注意这里的dp[i]只表示到达第i层时的花费并不包括在第i层本身需要支付的费用。
二、考虑状态转移
接下来我们要思考如何从一层楼到达另一层楼并计算出最小花费。 从第i-1层上来如果我们从第i-1层爬上来那么到达第i层的总花费就是dp[i-1] cost[i-1]其中cost[i-1]是第i-1层的费用。 从第i-2层上来另一种可能的情况是我们从第i-2层直接跳到第i层假设有这样的跳跃能力。那么到达第i层的总花费就是dp[i-2] cost[i-2]。
我们需要比较这两种情况选择花费更小的那种方式。
三、初始化状态
在开始计算之前我们需要给状态表一个起点。显然站在第一层或第二层是不需要花费的所以dp[0] dp[1] 0。
四、填表顺序
按照我们前面讨论的状态转移过程我们需要从左往右依次计算每一层的最小花费直到最后一层。
五、得出结果
最后当我们填满整个状态表后dp[n]就代表了到达最顶层的最小花费这就是我们要求的答案。
3.代码编写
class Solution
{
public:int minCostClimbingStairs(vectorint cost) {int n cost.size();vectorint dp(n 1);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];}
};
The Last
嗯就是这样啦文章到这里就结束啦真心感谢你花时间来读。
觉得有点收获的话不妨给我点个赞吧
如果发现文章有啥漏洞或错误的地方欢迎私信我或者在评论里提醒一声~
