深圳网站建设工资,合肥做网站好的公司,门户网站建设与运行,开发者官网前言
调整一下做题顺序#xff0c;多个章节同步进行#xff0c;穿插练习。可以在各章节的专栏中找同一类。
记录 六十九【动态规划基础】。
一、动态规划理论基础学习
参考学习链接 二、509. 斐波那契数
2.1 题目阅读
斐波那契数 #xff08;通常用 F(n) 表示#x…前言
调整一下做题顺序多个章节同步进行穿插练习。可以在各章节的专栏中找同一类。
记录 六十九【动态规划基础】。
一、动态规划理论基础学习
参考学习链接 二、509. 斐波那契数
2.1 题目阅读
斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是
F(0) 0F(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 302.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) {vectorint 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(n1,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];}
};三、总结 欢迎指正转载标明出处
