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