当前位置：首页 > news >正文

算法力扣刷题记录六十九【动态规划基础及509. 斐波那契数】

news 来源：原创 2024/9/21 5:43:30

前言

调整一下做题顺序，多个章节同步进行，穿插练习。可以在各章节的专栏中找同一类。

记录六十九【动态规划基础】。

一、动态规划理论基础学习

参考学习链接
在这里插入图片描述

二、509. 斐波那契数

2.1 题目阅读

斐波那契数（通常用 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

2.2 尝试实现

思路1

题目分析：虽然这道题放在了动态规划方法的下面。但是拿到题应该先判断这个能用什么方法。
学二叉树和回溯的时候，递归函数写的不错。那么递归能不能完成呢？感觉求F(n) = F(n-1) + F(n-2)是一个重复调用的过程，有点循环执行同一段代码的过程。
递归三部曲：

确定函数参数：int n；
确定函数返回值：返回F(n)。所以类型是int；直接用给的主函数fit。
确定终止条件：F(0) =0和F(1)=1不符合统一公式，所以有两个终止条件；
确定逻辑：return fit(n-1)+fit(n-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);}
};

思路2

用动态规划来做。动态规划解决当前状态可以由之前状态推导而得。本题的状态递推公式：F(n) = F(n - 1) + F(n - 2)。
第一步：确定dp数组的含义和下标。一维数组足够。下标代表n。数值代表F(n)。初始为31个，因为n <= 30；
第二步：初始化dp数组。前两个特殊的值： dp[0] =0; dp[1] = 1;
第三步：遍历数组。因为递推公式是从前往后，所以遍历顺序是从前往后。for循环初始为下标2。
第四步：return dp[n]。

代码实现【动态规划】

把vector dp(31,0);改成静态数组 int dp[31];但是静态数组的值应该是随机的。不过for循环依次填充可以先放着。

class Solution {
public:int fib(int n) {vector<int> dp(31,0);//下标代表n。数值代表F(n)//初始化,前两个特殊。其实dp[0] =0;dp[1] = 1;//遍历填充数组for(int i = 2;i <= n;i++){//递推公式dp[i] = dp[i-1]+dp[i-2];}return dp[n];}
};

2.3 参考学习

参考学习链接

五部曲在2.2思路2中已经分析；但是对比参考代码，可以修改的地方有：

dp数组根据传入的参数n来确定。vector< int> dp(n+1,0);之后初始化。

进一步 “状态压缩”，只维护两个数值。这样dp[2]；用中间变量sum记录F(n)。dp[0]更新为dp[1]，dp[1]更新为sum。

class Solution {
public:int fib(int N) {if (N <= 1) return N;int dp[2];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= N; i++) {int sum = dp[0] + dp[1];dp[0] = dp[1];dp[1] = sum;}return dp[1];}
};