【前言】
今天是刷题打卡第52天！
今天是成为原创博主的第60天，一转眼马上两个月过去了鸭，坚持似乎也不是特别难的事，加油吧亲们。
原题： 斐波那契数列（记忆化搜索、简单DP）
题目描述：
示例1：
输入：2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例2：
输入：3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
方法一：暴力递归
代码执行：
class Solution { public: int fib(int n){ //方法一：暴力递归 //找边界 if(n == 0){ return 0; } if(n == 1){ return 1; } return fib(n - 1) + fib(n - 2); } };
上面的代码存在的问题：
出现了大量的重复计算，比如：
方法二：循环求解
代码执行：
【敲黑板】：需要注意对于循环体的书写，以及循环条件，可能不是我们想象中那样的平移过程。
class Solution { public: int fib(int n){ //方法二：循环解决 int a = 0; int b = 1; int cur = 0; for(int i = 1; i <= n; i++)//当n为0时直接cur = 0 { cur = a + b; b = a; a = cur; } return cur; } };
方法三：记忆化搜索（简单DP）
思路：
即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。
一般使用一个数组充当这个「备忘录」，当然你也可以使用哈希表（字典），思想都是一样的。
class Solution { public: int fib(int n){ //方法三：记忆化搜索（简单DP） //找边界 if(n == 0){ return 0; } if(n == 1){ return 1; } //需要定义一个大小为(n+1)的整形数组，并且初始化为0 //之所以是n+1,是因为要使用到n这个下标 vector<int> dp(n+1, 0); dp[0] = 0; dp[1] = 1; for(int i = 2; i < n+1; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } };
结语
今天是刷题打卡第52天！
加油吧少年。
