98建筑网站,网页设计快速培训,郑州小程序开发多少钱,怎么搭建网站 优帮云【力扣】746. 使用最小花费爬楼梯
给你一个整数数组 cost #xff0c;其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用#xff0c;即可选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶…【力扣】746. 使用最小花费爬楼梯
给你一个整数数组 cost 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1 输入cost [10,15,20] 输出15 解释 你将从下标为 1 的台阶开始。 支付 15 向上爬两个台阶到达楼梯顶部。 总花费为 15 。
示例 2 输入cost [1,100,1,1,1,100,1,1,100,1] 输出6 解释你将从下标为 0 的台阶开始。 支付 1 向上爬两个台阶到达下标为 2 的台阶。 支付 1 向上爬两个台阶到达下标为 4 的台阶。 支付 1 向上爬两个台阶到达下标为 6 的台阶。 支付 1 向上爬一个台阶到达下标为 7 的台阶。 支付 1 向上爬两个台阶到达下标为 9 的台阶。 支付 1 向上爬一个台阶到达楼梯顶部。 总花费为 6 。
提示 2 cost.length 1000 0 cost[i] 999
题解
确定 dp 数组以及下标的含义 dp[i] 的定义为到达第 i 台阶所花费的最少体力为 dp[i] 。确定递推公式 有两个途径得到 dp[i]一个是 dp[i-1] 一个是 dp[i-2] dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] cost[i - 1] dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] cost[i - 2] 选最小的状态转移方程 dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);dp 数组如何初始化 选择从下标为 0 或下标为 1 的台阶开始爬楼梯dp[0] 0dp[1] 0确定遍历顺序 从前向后遍历举例推导 dp 数组打印 dp 数组
class Solution {public int minCostClimbingStairs(int[] cost) {int len cost.length;int[] dp new int[len 1];// 从下标为 0 或下标为 1 的台阶开始没跳没费用dp[0] 0;dp[1] 0;// 遍历for (int i 2; i len; i) {dp[i] Math.min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);}return dp[len];}
}
