leetcode746号问题

Question

数组的每个索引做为一个阶梯，第 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]逻辑就没问题，难道选择还和第四个数有关系？不知道怎么办了，求老师解答一下。

Answer 1

liuyubobobo 2018-10-30 02:48:04

典型的动态规划问题。

如果你熟悉动态规划的思路的话，会觉得非常简单。

设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++）：

https://github.com/liuyubobobo/Play-Leetcode/blob/master/0746-Min-Cost-Climbing-Stairs/cpp-0746/main.cpp

如果你没有接触过动态规划，不了解动态规划，可能会觉得很难入手。这个问题之所以easy，是因为属于动态规划中最简单的问题：）

如果对动态规划感兴趣，推荐一下我的《玩转算法面试》课程：）https://coding.imooc.com/class/82.html

另外，Leetcode的70号问题，是这个问题的另一个版本，也属于动态规划的简单问题，有兴趣可以试试看：https://leetcode.com/problems/climbing-stairs/ ：）

加油！：）

• 提问者 落叶灯花 #1

  非常感谢！

• 提问者 落叶灯花 #2

  老师，递推的方法我会了：    public static int minCostClimbingStairs(int[] cost) {
          int sum = 0;
          ArrayList<Integer> castArray = new ArrayList<>();
          castArray.add(0);
          for (int i = 0; i < cost.length; i++) {
              castArray.add(cost[i]);
          }
  
          ArrayList<Integer> outPutArray = new ArrayList<>();
          for (int i = 0; i <= castArray.size(); i++) {
              if (i == 0 || i == 1)
                  outPutArray.add(0);
              else {
                  int min = Math.min(outPutArray.get(i - 2) + castArray.get(i - 2), outPutArray.get(i - 1) + castArray.get(i - 1));
                  outPutArray.add(min);
              }
          }
          sum = outPutArray.get(outPutArray.size() - 1);
          return sum;
      }
  但是递归的解法还是想不出来，递归的解法是不是要用到链表呢？请老师提点

• liuyubobobo 回复 提问者 落叶灯花 #3

  转移方程就是递归式啊！相应的技术叫记忆化搜索。建议学习我的《玩转算法面试》学习一下。也可以参考我的70号问题的递归写法，看是否有所启发？https://github.com/liuyubobobo/Play-Leetcode/blob/master/0070-Climbing-Stairs/cpp-0070/main.cpp 加油！