🎉 【动态规划算法题】- 斐波那契类型

Leecode 70. 爬楼梯

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

1 <= n <= 45

解题思路

动态规划的解题关键在于用表格存储局部解的结果，再用局部解来递推求最终结果，其中最关键的点就在于如何建立递推公式。

对于本题中，可以先从简单情形开始考虑：

1层楼梯时，只有1种方法；
2层楼梯时，有2种方法；
3层楼梯时，可以一步跨两阶走到还剩1层，也可以只跨一阶走到还剩2层，因此方法的数量为1层和2层的方法数量之和；
4层楼梯时，和3层时的情况相似，方法数量为还剩2层和还剩3层时之和；
$\cdots$
n层楼梯时，可以跨两阶走到还剩n-2层，也可以跨一阶走到还剩n-1层由上面思路可以得到还剩$n$层时爬楼梯的方法数量$a_n$的递推公式： $$a_n = a_{n-1} + a_{n-2}$$ 其中$n >= 3$，且有初值$a_1 = 1$，$a_2 = 2$。由此可以写出代码如下：

class Solution {
public:
    int climbStairs(int n) {
        int arr[46]; // 建立数组用于存储结果
        arr[1] = 1; // 只有一阶时
        arr[2] = 2; // 只有两阶时
        for(int i = 3; i < 46; i++){
            arr[i] = arr[i-1] + arr[i-2]; // 递推公式
        }
        return arr[n];
    }
};

对于上面代码，可以估算时间复杂度为$O(n)$，即只需要遍历一遍整个数组即可计算出所有剩余楼层数的情况并存入数组中，最后输出时再查表输出即可。这种**“存表格”的方式，就是所谓的动态规划**，是用表格存储的空间来换时间。

为了体现动态规划的好处，这里尝试使用递归的方式来实现一下：

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        return climbStairs(n-1) + climbStairs(n-2); // 递归实现递推公式
    }
};

在上面代码中，每次计算$a_{n}$都需要递归调用计算$a_{n-1}$和$a_{n-2}$两部分，且又可以注意到当计算$a_{n-1}$的时候还需要再次计算$a_{n-2}$，显然其中计算的时间复杂度特别高，估算后为$O(2^n)$，相比之前的$O(n)$而言时间复杂度特别之大，从而可以看出动态规划显著降低了时间复杂度。

Leecode 509. 斐波那契数

题目描述

斐波那契数（通常用 F(n) 表示）形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给定 n ，请计算 F(n) 。
示例 1：

输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

0 <= n <= 30

解题思路

本题是很经典的斐波那契数列，和上一题的计算方式非常相似，根据递推公式可以直接计算并存储到数组中，然后再查表输出。由此可以写出代码如下：

class Solution {
public:
    int fib(int n) {
        int dp[3] = {0};
        dp[1] = 1;
        for(int i = 2; i <= n; i++) dp[i%3] = dp[(i-1)%3] + dp[(i-2)%3]; // 仅使用长度为3的数组存储
        return dp[(n)%3];
    }
};

上面这段代码中，仅使用了一个长度为3的数组来进行存储，其中两个用于存储前两个数的结果，用一个来计算两数之和并存储。由此控制空间复杂度为$O(1)$，同时时间复杂度为$O(n)$。

Leecode 1137. 第 N 个泰波那契数

题目描述

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例 1：

输入：n = 4 输出：4 解释： T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4

示例 2：

输入：n = 25 输出：1389537

提示：

0 <= n <= 37 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。

题目解析

首先需要注意本题不是一般的斐波那契数列，而是泰波那契数列，即为前3个数之和，此外其余和之前的斐波那契数列并没有太多差别。

思路同样都是，先计算建表，再查表输出。

class Solution {
public: 
    int tribonacci(int n) {
        vector<int> arr(38,0); // 建立长度为38的数组
        arr[1] = arr[2] = 1; // 前三个值为0, 1, 1
        for(int i = 3; i <= n; i++){
            arr[i] = arr[i-1] + arr[i-2] + arr[i-3];  // 递归计算填表
        }
        return arr[n];
    }
};

直接使用上面代码即可计算这个泰波那契数列，时间复杂度为$O(n)$。

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

题目解析

要计算爬完楼梯所用的最少花费，同样也可以使用动态规划的方法，使用一个表格来存储局部的最优解，最后通过查表输出结果。关键在于如何通过局部解递推更大的局部解，可以建立一个数组，用于存储该层楼梯到顶部还需的最少花费，最后输出即为第1阶和第2阶中花费中更小的一个。接下来我们分析如何构建这个数组。

首先从最简单的情况说起，如果只有1阶阶梯（或位于倒数第一阶阶梯），记录下其所需花费（注：题目中说明了阶梯长度最小为2），记作dp[size-1] = cost[size-1]
如果只有2个阶梯（或位于倒数第二阶阶梯），同样可以一步完成，此时花费为也为当前阶梯的花费，记作dp[size-2] = cost[size-2]
如果有3个阶梯（位于倒数第三阶阶梯），需要先走一步到倒数1阶或倒数2阶，此时最少花费为当前阶梯花费加上后续两种方式中花费更少的一个，即dp[size-3] = cost[size-3] + min(dp[size-2], dp[size-1])

通过上面这样的分析方式，可以给出数组dp的递推公式：dp[i] = cost[i] + min(dp[i+1], dp[i+2])

根据递推公式就可以写出代码如下：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size(), 0);
        dp[cost.size()-1] = cost[cost.size()-1];
        dp[cost.size()-2] = cost[cost.size()-2];

        for(int i = dp.size()-3; i >= 0; i--){
            dp[i] = cost[i] + min(dp[i+1], dp[i+2]);
        }
        return min(dp[0], dp[1]);
    }
};

最后返回输出初始两阶中更小的一个，相当于题目中描述的“ 可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯”。

198. 打家劫舍

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

1 <= nums.length <= 100 0 <= nums[i] <= 400

题目解析

本题“打家劫舍”是很经典的动态规划问题，在不可相邻的限制之下，要尽可能取到和的最大值。要采用动态规划，我们同样还是通过 计算建表 -> 查表输出 的范式来求解。可以考虑建立一个数组，用于存储“ 从第一个房屋到当前房屋的最大金额 ”，也还是通过数量更小的情况来分析：

对于第一个房屋，要金额最大则必须抢下这个房屋，有dp[0] = nums[0]
对于第两个房屋，只有两种可能，要么抢要么不抢；要使金额最大则有：dp[1] = max(nums[0], nums[1])
对于第三个房屋，也是要么抢要么不抢，则金额最大为：dp[2] = max(nums[2] + dp[1], dp[2])。
- 其中dp[2]表示当前不拿，则和上一个的最大金额一致；
- nums[2] + dp[1]表示当前拿，则相当于当前金额加上上间的最大金额

总结出最大金额的递推公式为：dp[i] = max(nums[i] + dp[i-2], dp[i-1])，则根据这个递推公式可以写出下面代码：

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];  // 只考虑一间时的最大收益
        dp[1] = max(nums[0], nums[1]);  // 考虑两间时的最大收益

        for(int i = 2; i < nums.size(); i++){
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);  // 计算考虑到第i+1间的最大收益
        }
        return dp[nums.size()-1]; // 查表输出考虑了最后一间的最大收益，即为全局最优解
    }
};

上面代码的时间复杂度为$O(n)$。

小结：本题关键点在于理解其中dp数组的意义，相当于存储了一个局部的最优解，并通过这样的局部解来递推求解更大的局部解，最终得到全局最优解。

740. 删除并获得点数

题目描述

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 1：

输入：nums = [3,4,2] 输出：6 解释：删除 4 获得 4 个点数，因此 3 也被删除。之后，删除 2 获得 2 个点数。总共获得 6 个点数。

示例 2：

输入：nums = [2,2,3,3,3,4] 输出：9 解释：删除 3 获得 3 个点数，接着要删除两个 2 和 4 。之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。总共获得 9 个点数。

提示：

1 <= nums.length <= 2 * 104 1 <= nums[i] <= 104

题目解析

本题和上一题的打家劫舍非常相似，但需要先对数据进行一些处理。首先因为是给定的数组中的相邻关系是乱序的，我们需要进行数据的统计，记录出每个数出现的频率。再计算每个数的全部分数，存储到一个新的数组count中。最后再对这个数组按照上一题中的方式求解即可。故可以写出代码如下：

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        vector<int> count(10001, 0);
        for(int i = 0; i < nums.size(); i++){
            count[nums[i]]++;  // 统计每个数出现频率
        }
        for(int i = 0; i < count.size(); i++){
            count[i] = count[i]*i;  // 计算每个数的频率和
        }
        
        vector<int> dp(10001, 0); // 建立dp数组，按之前打家劫舍问题求解
        dp[0] = count[0];
        dp[1] = max(count[0], count[1]);
        for(int i = 2; i < dp.size(); i++){
            dp[i] = max(dp[i-1], dp[i-2] + count[i]);
        }
        return dp[dp.size()-1];
    }
};

小结

本文讲解了几道动态规划中斐波那契类型问题，其中关键都在于建立递推公式，再将计算的结果存储到一个数组中，最后再通过查表输出。