dp第二天

「动态规划」 – 学习计划 – 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

70. 爬楼梯

这一题就比斐波那契数列要麻烦，看我下我的备注

/**
 70. 爬楼梯
 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

 示例 1：

 输入：n = 2
 输出：2
 解释：有两种方法可以爬到楼顶。
 1. 1 阶 + 1 阶
 2. 2 阶
 示例 2：

 输入：n = 3
 输出：3
 解释：有三种方法可以爬到楼顶。
 1. 1 阶 + 1 阶 + 1 阶
 2. 1 阶 + 2 阶
 3. 2 阶 + 1 阶


 提示：

 1 <= n <= 45


 * @author zeroheart
 *
 */
public class Question70 {

    public int climbStairs(int n) {
        /**
         *
         1. f(n) = f(n-1) + 1 = f(n-2) + 2
         2. f(n-1) = f(n-2) + 1
         3. f(n) = 2f(n-2) + 3
         上面是我一开始的错误推导，这个看似很合理，实际上最终f(n-1) = f(n-2) + 1这个不能这么写，f(n-2)如果往前走一步，到了f(n-1)，那么路径就固定了.
         我们要讨论的是f(n-2)的时候不能走到f(n-1)，就是说f(n-2)只能走两步直接到f(n),f(n-1)走一步直接到f(n)，这样子，问题就变成了到f(n-1)和f(n-2)的方法，得到f(n)=f(n-1)+f(n-2)
         我们对f(n)的定义，要时刻记得，这里f(n)是走到n的方法，推导成为走到f(n-1)的方法+f(n-2)的方法
         */
        if(n == 1) return 1;
        if(n == 2) return 2;
        if(n == 3) return 3;
        int[] r = new int[n+1];
        r[1] = 1;
        r[2] = 2;
        r[3] = 3;
        for(int i = 4; i <= n; i++){
            r[i] = r[i-1] + r[i-2];
            // r[i] = 2 * r[i-2] + 3; 错误的推导
        }
        return r[n];
    }

}

746. 使用最小花费爬楼梯

/**
 746. 使用最小花费爬楼梯
 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

 请你计算并返回达到楼梯顶部的最低花费。



 示例 1：

 输入：cost = [10,15,20]
 输出：15
 解释：你将从下标为 1 的台阶开始。
 - 支付 15 ，向上爬两个台阶，到达楼梯顶部。
 总花费为 15 。
 示例 2：

 输入：cost = [1,100,1,1,1,100,1,1,100,1]
 输出：6
 解释：你将从下标为 0 的台阶开始。
 - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
 - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
 - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
 - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
 - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
 - 支付 1 ，向上爬一个台阶，到达楼梯顶部。
 总花费为 6 。


 提示：

 2 <= cost.length <= 1000
 0 <= cost[i] <= 999

 * @author zeroheart
 *
 */
public class Question746 {
    public int minCostClimbingStairs(int[] cost) {
        /**
         * dp[i] 表示到i的最小cost
         * 可以得到公式
         * dp[i] = min(dp[i-1] + cost[i-1] , dp[i-2] + cost[i-2])
         */
        int[] dp = new int[cost.length+1];
        dp[0] = 0;
        dp[1] = 0;
        for(int i = 2; i <= cost.length; i++){
            dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }
        return dp[cost.length];
    }
}