剑指offer88：爬楼梯的最少成本

题目：

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。

请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 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 。

分析：

该题每次爬的时候既可以往上爬1级台阶也可以爬两级台阶，也就是说每一步都有两个选择。看似这与回溯法有关，但这个问题不是要找出有多少种方法可以爬上楼梯，而是要计算爬上楼梯的最少成本，即计算问题的最优解，因此这个问题更适合动态规划。

针对动态规划方法，首先我们就要确定状态转移方程，可以用f（i）表示从楼梯的第i级台阶再往上爬的最少成本。如果一个楼梯有n级台阶（台阶从0级一直到第n-1级），由于一次可以爬1级或2级台阶，因此可以从第n-2级台阶或第n-1级台阶爬到楼梯的顶部，即f(n-1)和f(n-2)的最小值就是这个问题的最优解。从第i级台阶往上爬的最少成本应该是从第i-1级台阶往上爬的最少成本和从第i-2级台阶往上爬的最少成本的较小值再加上第爬第i级台阶的成本=》f(i)=min(f(i-1),f(i-2))+cos[i]。该方程有个隐含条件，即i大于等于2，如果i等于0，则可以直接从第0级台阶往上爬。f(0)=cos[0],如果i等于1，题目中提到可以从第1级台阶出发往上爬，因此f(1)=cos[1]。

该题有四种解法：

圈9代表f(9)，第一种解法代码看似简单，但是时间复杂度十分糟糕，例如f（6）需要计算很多次，其实只要计算一次就够了，其他的计算都是多余的，所以我们需要剪枝操作来，也就是第二种解法，避免重复计算，利用数组来存储结果。

或者我们可以换一种思路从下而上来解决这个过程，也就是从子问题入手，根据两个子问题f（i-1）和f（i-2）的解求出f（i）的结果。第四种思路是在第三种思路的基础上优化，主要是为了降低空间复杂度，前面利用了一个长度为n的数组将所有f（i）的结果都保存下来，求解f（i）的结果都保存下来。但求解f（i）时只需要f（i-1）和f（i-2）的的结果，从0到f（i-3）的结果其实对求解f(i)没有任何作用，因此只需要一个长度为2的数组就可以了，具体看代码。

代码：

import java.util.Map;

public class MinCostClimbingStairs {
    public static void main(String[] args) {
        MinCostClimbingStairs minCostClimbingStairs = new MinCostClimbingStairs();
        int[] cost = {1,100,1,1,100,1};
        int i = minCostClimbingStairs.minCostClimbingStairs3(cost);
        System.out.println(i);
    }
    public int minCostClimbingStairs(int[] cost){
        int len = cost.length;
        return Math.min(helper1(cost,len-2),helper1(cost,len-1));
    }

    private int helper1(int[] cost, int i) {
        if (i<2){
            return cost[i];
        }
        return Math.min(helper1(cost,i-1),helper1(cost,i-2))+cost[i];
    }
//利用数组来存储结果
    public int minCostClimbingStairs1(int[] cost) {
        int len = cost.length;、
        //该数组的每个元素都初始化为0
        int[] dp = new int[len];
        helper(cost,len-1,dp);
        return Math.min(dp[len - 2],dp[len - 1]);
    }

    private void helper(int[] cost, int i, int[] dp) {
        if (i < 2){
            dp[i] = cost[i];
            //由于每级台阶往上爬的成本都是正数，因此如果某个问题f(i)之前已经求解过了，那么一定是一个大于0的数值。
        }else if (dp[i] == 0){
            helper(cost,i-2,dp);
            helper(cost,i-1,dp);
            dp[i] = Math.min(dp[i-2],dp[i-1])+cost[i];
        }
    }
//    自下而上，这个思路感觉要比自上而下的思路更好想
    public int minCostClimbingStairs2(int[] cost){
        int len = cost.length;
        int[] dp = new int[len];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < len; i++) {
            dp[i] = Math.min(dp[i-1],dp[i-2])+cost[i];
        }
        return Math.min(dp[len-2],dp[len-1]);
    }
    //优化空间复杂度解法
    public int minCostClimbingStairs3(int[] cost){
        int[] dp = new int[]{cost[0],cost[1]};
        for (int i = 2; i < cost.length; i++) {
//            用f(i)的结果覆盖f(i-2)的结果并不会带来任何问题
//            dp[0] 从开始到最终分别对应的是下标为0 2 4 6...的数组值,dp[1]同理。
//            求解的f（i）的结果保存在数组下标为“i%2”的位置。
            dp[i%2] = Math.min(dp[0],dp[1]) + cost[i];
        }
        return Math.min(dp[0],dp[1]);
    }
}