题解 | #最小花费爬楼梯#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int minCostClimbingStairs (int[] cost) {
        // write code here
        // 动态规划问题，类似斐波那契数列
        // 状态转移方程 dp[i] = min(dp[i-1],dp[i-2])+cost[i]
        // 方程的含义是，从dp[i]出发的花费，有之前的dp花费，加上当前楼层的花费
        int n = cost.length;
        if(n == 0){
            return 0;
        }
        // 从0层走一步到1层，1层不用付费
        if(n == 1){
            return cost[0];
        }
        // 比如数组大小为n，也就是0-n-1，但是题目求得是到顶层，即n层的花费
        int[] dp = new int [n+1];
        // 从零层出发
        dp[0] = cost[0];
        // 从1层出发
        dp[1] = cost[1];
        for(int i =2; i <= n ; i++){
            // 如果刚好到底层，就不用再花费了
            int costValue = (i == n ) ? 0 : cost[i];
            dp[i] = Math.min(dp[i-1], dp[i-2]) + costValue;
        }
        return dp[n];
    }
}

题目意思不太好理解，数组表示的是当层楼的收费，如果收费说明你得离开，走一步或者两步。

特殊情况，空数组，return 0 ；如果只输入一个数字，那就是走一级，cost[0]

递推，如果是数组长度为2，可以是从1的时候出发，走一步到达2，也可以是从0出发走两步到2。从0出发cost[0]，从1出发cost[1]。

所以在递推关系中，刺客站在dp[i]，i级楼层也是付费的，它可以使从i-1到的，也可是从i-2到的，到了之后再付费cost[i]。如果刚好到顶楼，是不用付费的，因为你不用再往上走了，确实这样，cost数组也没有提供cost[n]的数值。