代码随想录算法训练营第三十八天 | 斐波那契数、爬楼梯、使用最小花费爬楼梯

509. 斐波那契数

题目链接：509. 斐波那契数

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

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

文章讲解/视频讲解：https://programmercarl.com/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.html

思路

很简单的动规题，dp数组中每个下标dp[i]代表F(i)，初始化方式题目已经给出，即dp[0] = 0, dp[1] = 1。

递推公式是dp[i] = dp[i - 1] + dp[i - 2]，遍历方向是从前向后。

因为递推公式只用到了dp数组的前两个值，因此可以不单独开辟一个数组，用pre1，pre2代表dp数组中的前两个值。即递推公式变成：cur = pre1 + pre2。

C++实现

class Solution {
public:
    int fib(int n) {
        if(n == 0 || n == 1) return n; 
        int pre1 = 1, pre2 = 0;
        int cur;
        for(int i = 2;i<=n;i++){
            cur = pre1 + pre2;
            pre2 = pre1;
            pre1 = cur;
        }
        return cur;
    }
};

70. 爬楼梯

题目链接：70. 爬楼梯

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

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

文章讲解/视频讲解：https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF.html

思路

首先确定dp数组中每个下标的含义，每个下标i代表爬i阶楼梯一共有多少种方法。

初始化时，令dp[0] =1， dp[1] = 1，dp[1] = 1好理解，dp[0]可以从示意中看出，dp[2] = dp[0] + dp[1] = 2，因此dp[0] = 1，dp[1] = 1。

dp数组的递推公式为：dp[i] = dp[i - 1] + dp[i - 2]。

与上一题类似，因为递推公式只用到了前两个值，可以用pre1, pre2代替。

C++实现

class Solution {
public:
    int climbStairs(int n) {
        if(n == 0 || n == 1) return 1;
        int pre1 = 1, pre2 = 1;
        int cur;
        for(int i = 2;i<=n;i++){
            cur = pre1 + pre2;
            pre2 = pre1;
            pre1 = cur;
        }
        return cur;
    }
};

746. 使用最小花费爬楼梯

题目链接：746. 使用最小花费爬楼梯

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

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

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

文章讲解/视频讲解：https://programmercarl.com/0746.%E4%BD%BF%E7%94%A8%E6%9C%80%E5%B0%8F%E8%8A%B1%E8%B4%B9%E7%88%AC%E6%A5%BC%E6%A2%AF.html

思路

dp[i]代表爬到下标为i的台阶，所需要的最小花费。因为可以从下标为0或者下标为1的台阶开始爬楼梯，因此dp[0] = 0,dp[1] = 0。

递推公式为dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);遍历方向为从左向右遍历。

代入示例1，dp[2] = min(dp[0] + 10, dp[1] + 15) = 10，dp[3] = min(dp[1] + 15, dp[2] + 20) = 15，结果正确。

和前两题类似，因为递推公式中只用到了前两项，可以用pre1，pre2代替dp数组。

C++实现

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int pre1 = 0, pre2 = 0;
        int cur = 0;
        for(int i = 2;i<=cost.size();i++){
            cur = min(pre1 + cost[i - 1], pre2 + cost[i - 2]);
            pre2 = pre1;
            pre1 = cur;
        }

        return cur;
    }
};