怎么通过淘宝优惠券做网站赚钱,tp框架做网站的优点,wordpress首页只显示一篇文章,wordpress 水印题目 给定一个整数数组 cost #xff0c;其中 cost[i] 是从楼梯第i 个台阶向上爬需要支付的费用#xff0c;下标从0开始。一旦你支付此费用#xff0c;即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的…题目 给定一个整数数组 cost 其中 cost[i] 是从楼梯第i 个台阶向上爬需要支付的费用下标从0开始。一旦你支付此费用即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
数据范围数组长度满足 1≤n≤105数组中的值满足 1≤costi≤104
示例1
输入
[2,5,20]
返回值
5
说明
你将从下标为1的台阶开始支付5 向上爬两个台阶到达楼梯顶部。总花费为5 示例2
输入
[1,100,1,1,1,90,1,1,80,1]
返回值
6
说明
你将从下标为 0 的台阶开始。
1.支付 1 向上爬两个台阶到达下标为 2 的台阶。
2.支付 1 向上爬两个台阶到达下标为 4 的台阶。
3.支付 1 向上爬两个台阶到达下标为 6 的台阶。
4.支付 1 向上爬一个台阶到达下标为 7 的台阶。
5.支付 1 向上爬两个台阶到达下标为 9 的台阶。
6.支付 1 向上爬一个台阶到达楼梯顶部。
总花费为 6 。思路 题目考察斐波那契数列的动态规划实现不同的是题目要求了最小的花费因此我们将方案统计进行递推的时候只记录最小的开销方案即可。
可以用一个数组记录每次爬到第i阶楼梯的最小花费然后每增加一级台阶就转移一次状态最终得到结果。
因为可以直接从第0级或是第1级台阶开始因此这两级的花费都直接为0。
每次到一个台阶只有两种情况要么是它前一级台阶向上一步要么是它前两级的台阶向上两步因为在前面的台阶花费我们都得到了因此每次更新最小值即可转移方程为min_cost[i]min(min_cost[i−1]cost[i−1],min_cost[i−2]cost[i−2])。 解答代码 #include algorithm
#include vector
class Solution {
public:/*** param cost int整型vector * return int整型*/int minCostClimbingStairs(vectorint cost) {// write code hereauto size cost.size();if (size 3) {return 0;}std::vectorint min_cost(size1, 0);//记录每移动一次的最小花费for (int i 2; i size; i) {min_cost[i] std::min(cost[i-1] min_cost[i-1], cost[i-2] min_cost[i-2]);}return min_cost[size];}
};
