leetcode746号问题
来源：8-8 Java中的PriorityQueue
落叶灯花
2018-10-29
数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 costi。
每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
示例 1:
输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
示例 2:
输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
注意：
cost 的长度将会在 [2, 1000]。
每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。
我的代码：
import java.util.ArrayList;
public class Solution {
public static int minCostClimbingStairs(int[] cost) {
int sum = 0;
System.out.println(cost.length);
for (int i = -1; i < cost.length - 2; i++) {
if(cost[i + 1]==cost[i + 2]){
int biggger = Math.min(cost[i + 1], cost[i + 2]);
sum += biggger;
int index = i+2;
i = index - 1;
}
else {
int biggger = Math.min(cost[i + 1], cost[i + 2]);
sum += biggger;
int index = (biggger == cost[i + 1] ? i + 1 : i + 2);
i = index - 1;
}
}
return sum;
}
}
这个问题是个简单问题，总觉得应该和数组的个数有关系，我之前的逻辑是前面的第二个数>第一个数+第三个数？跳一步：跳两步。遇到[0,1,2,2]也是错的，我在想如果是 [0,1,2]逻辑就没问题，难道选择还和第四个数有关系？不知道怎么办了，求老师解答一下。
1回答
-
典型的动态规划问题。
如果你熟悉动态规划的思路的话，会觉得非常简单。
设f(i)是到第i层所需要的最小耗费，则：
f(i) = min(f(i - 1) + cost(i - 1), f(i - 2) + cost(i - 2))
翻译成自然语言就是：
到第i层的最小耗费，是比较一下，是从 i - 1 层爬到第 i 层耗费小？还是从 i - 2层爬到第 i 层耗费小？取小的。
从 i - 1 层爬到第 i 层的耗费，是爬到 i - 1 层的最小耗费，加上cost[i - 1]；
从 i - 2 层爬到第 i 层的耗费，是爬到 i - 2 层的最小耗费，加上cost[i - 2]；
基础条件：f(0) = f(1) = 0，即爬到第0层和第1层不需要耗费。
有了上面的式子，用递推，递归解决，都可以。动态规划的思想是递推的思想，可以参考我的代码（C++）：
如果你没有接触过动态规划，不了解动态规划，可能会觉得很难入手。这个问题之所以easy，是因为属于动态规划中最简单的问题：）
如果对动态规划感兴趣，推荐一下我的《玩转算法面试》课程：）https://coding.imooc.com/class/82.html
另外，Leetcode的70号问题，是这个问题的另一个版本，也属于动态规划的简单问题，有兴趣可以试试看：https://leetcode.com/problems/climbing-stairs/ ：）
加油！：）
232018-11-03
相似问题