当前位置: 代码迷 >> 综合 >> JAVA算法:爬楼梯的最小代价(花费成本)
  详细解决方案

JAVA算法:爬楼梯的最小代价(花费成本)

热度:3   发布时间:2024-01-15 19:18:44.0

JAVA算法:爬楼梯的最小代价(花费成本)

给定一个数组cost,其中cost[i]的值就代表着你爬第[i]阶的台阶的开销。一旦你付了这个开销,你就可以继续往上爬一阶或者两阶,知道你达到最顶层(数组的结尾元素再多一层)。同时你可以选择从第0阶开始或者第一阶开始。
我们的目标是找出你爬到最顶层所付出的最小的开销。

Example 1:
Input: cost = [10, 15, 20]
Output: 15
Explanation: 最低开销是,从第1阶(15)开始,只花费15就可以到顶层。
Example 2:
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: 最低开销是,从第0阶开始(1),然后只走值为1的台阶,其中跳过第3阶。


算法分析

  • 动态规划问题。
  • 新建一个数组minCost,用它来保存走到第 i 阶所消耗的最低开销。
  • minCost的长度应该为cost数组长度加一,其中mincost数组的最后一个元素的值就是本题的答案,最低开销。

算法设计

public int minCostClimbingStairs(int[] cost) {int minCost[] = new int[cost.length+1];minCost[0] = cost[0];minCost[1] = cos