1.简述: 描述 给定一个整数数组 ,其中 是从楼梯第 个台阶向上爬需要支付的费用,下标从0开始。一旦你支付此费用,即可选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下
1.简述:
描述给定一个整数数组 ,其中 是从楼梯第个台阶向上爬需要支付的费用,下标从0开始。一旦你支付此费用,即可选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
数据范围:数组长度满足 ,数组中的值满足
输入描述:第一行输入一个正整数 n ,表示数组 cost 的长度。
第二行输入 n 个正整数,表示数组 cost 的值。
输出描述:输出最低花费
示例1输入:
32 5 20
输出:
5说明:
你将从下标为1的台阶开始,支付5 ,向上爬两个台阶,到达楼梯顶部。总花费为5示例2输入:
101 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 。
2.代码实现:
import java.util.Scanner;public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] cost = new int[in.nextInt()];
for (int i = 0; i < cost.length; i++) {
cost[i] = in.nextInt();
}
System.out.println(minCostClimbingStairs(cost));
}
private static int minCostClimbingStairs(int[] cost) {
int[] dp = new int[cost.length + 1];
for (int i = 2; i <= cost.length; i++) {
dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
}
return dp[cost.length];
}
}