城市网站建设分析报告,html个人网站源码,云服务器 虚拟机,旅游网站建设经济评价题目链接#xff1a;leetcode使用最小花费爬楼梯 目录
题目解析#xff1a;
算法原理
1.状态表示
2.状态转移方程
3.初始化
4.填表顺序
5.返回值
编写代码 题目解析#xff1a; 题目让我们求达到楼梯顶部的最低花费.
由题可得#xff1a; cost[i] 是从楼梯第 i 个…题目链接leetcode使用最小花费爬楼梯 目录
题目解析
算法原理
1.状态表示
2.状态转移方程
3.初始化
4.填表顺序
5.返回值
编写代码 题目解析 题目让我们求达到楼梯顶部的最低花费.
由题可得 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用每一阶所需的费用由cost[ ]里的值决定。
可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯支付费用后可选择向上爬一个或者两个台阶
那么楼顶在哪
我们从题目里的实例一来分析
如果楼顶是i那么这里的最小花费为应该为10但是这里输出是15 所以楼顶是在这里 算法原理:
1.状态表示
先创建一个dp表 首先先思考dp表里面的值所表示的含义是什么
dp[i]表示在到达i位置的最小花费 这种状态表示怎么来的
1.经验题目要求
经验以i位置为结尾
题目让我们求达到楼梯顶部的最低花费那么这里我们可以dp[i]来表示。
所以这里我们用i表示楼顶 2.状态转移方程
dp[i]等于什么
用之前或者之后的状态推导出dp[i]的值
根据最近的最近的一步来划分问题 我们这里有两种情况
第一种
到达i-2是最小花费支付cost[i-2]后跳两步到达楼顶
第一种
到达i-1是最小花费支付cost[i-1]后跳一步到达楼顶
所以 这里我们只要返回这两种情况的最小值就可以了
我们这里会用到min 综上所述
dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]) 3.初始化
(保证填表的时候不越界)
由题目得
在第01阶的时候是不用花费的
所以这里要初始化为0 4.填表顺序
为了填写当前状态的时候所需要的状态已经计算过了
这里所需要的状态是dp[i-1]、dp[i-2]
这几个数都是在i之前的
所以我们这里是从左向右填表 5.返回值
根据题目要求和状态表示
综上分析
返回值为dp[n] 编写代码: class Solution {
public:int minCostClimbingStairs(vectorint cost) {//1.创建dp表//2.初始化//3.填表//4.返回结果int ncost.size();vector int dp(n1);//因为vector会把表里初始化为0所以这里我们不用考虑初始化的情况for(int i2;in;i){dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);}return dp[n];}
};
