day38 动态规划part1

509. 斐波那契数

简单
斐波那契数（通常用 F(n) 表示）形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。

class Solution {
    public int fib(int n) {
        if (n < 2) return n;

        int dpa = 0;
        int dpb = 1;
        int dpc = 0;

        for (int i = 2; i <= n; i++) {
            dpc = dpa + dpb;
            dpa = dpb;
            dpb = dpc;
        }

        return dpc;
    }
}

70. 爬楼梯

简单
提示
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

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

没做过的话觉得好难，其实是有规律的，因为每次只能跳一或者两个台阶，所以，要想跳到f（n）,就必须跳到f(n - 1) 或者 f(n - 2)，所以f(n) = f(n - 1) + f(n - 2) , 有人可能会讲，f(n - 1) 和 f(n - 2) 里有没有重合的跳法，因为f(n - 1) 必然经过 f(n - 2)，这就有点问题了，因为f(x) 表示爬到第 x 级台阶的方案数，题目让你求得是方案数，不是爬楼梯的步数。f(n) = f(n - 1) + f(n - 2) 不能再加2哈，因为你到了f(n - 1)只有这种方案能上楼，f(n - 2)同理，记住，是方案的数量，不是上楼的步数。不要去管f(n - 1) 和f(n - 2)，有联系，是有联系，可以没让你去管啊，要管的事f(n) 的算法。说再多没用，自己模拟前4个台阶怎么算的就明白了。

在这里插入图片描述

class Solution {
    public int climbStairs(int n) {
        if (n < 3) return n;

        int step1 = 1;
        int step2 = 2;
        int step3 = 0;
        for (int i = 3; i <= n; i++) {
            step3 = step1 + step2;
            step1 = step2;
            step2 = step3;
        }

        return step3;
    }
}

746. 使用最小花费爬楼梯

简单
提示
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费

// 这个题也可以不用dp数组，就三个变量就行
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]
        int[] dp = new int[cost.length + 1]; // 把顶层也算上，多分配一个空间
        dp[0] = dp[1] = 0; // 可以选择从下标为 0 或下标为 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];
    }
}