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

dp：斐波那契变种

和fibbo的区别：

1. dp[i]的组成不光是dp[i-1]和dp[i-2]，还有他们对应的代价cost[i-1]，cost[i-2]
2. dp[i] 取的是 dp[i-1]+cost[i-1] 和 dp[i-2]+cost[i-2] 中的小值

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int minCostClimbingStairs (int[] cost) {
        int len = cost.length;
        int[] dp = new int[len + 1];
        dp[0] = 0;
        dp[1] = 0;
        // dp[i] 表示到达第i级阶梯需要的最小花费为 dp[i]
        for (int i = 2; i < len+1; ++i) {
            // 在 i 处可以从 i-1 跳上来，也可以从 i-2 处跳上来
            // 从 i-1 跳上来的代价就是 dp[i-1] + 在 i-1 处的代价 cost[i-1]
            // 从 i-2 跳上来的代价就是 dp[i-2] + 在 i-2 处的代价 cost[i-2]
            // 因为 dp[i] 表示的是在 i 处的最小代价，因此二者取min即可
            dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }

        return dp[len];
    }
}