DP入场的斐波那契数

斐波那契数通常用F(n)表示，形成的数列称为斐波那契数列。该序列以0和1开头，后面的每个数字都是前两个数字的总和。即：F(0)=0,F(1)=1F(n)=F(n-1)+F(n-2)，其中n>1给你n，请计算F(n)。示例1：输入：2输出：1解释：F(2)=F(1)+F(0)=1+0=1示例2：输入：3输出：2解释：F(3)=F(2)+F(1)=1+1=2示例3：输入：4输出：3解释：F(4)=F(3)+F(2)=2+1=3提示：0<=n<=30Ideas斐波那契数列大家应该都非常熟悉，非常适合作为走势规律的第一题来练习。因为这个题目比较简单，有的同学可能不需要做任何分析，写下来就可以了。但《CodeCaprice》的风格是：用简单的问题来加深对解题方法论的理解。通过这道题，大家可以初步了解如何根据动态规则的五个部分来解题。对于motion的规则，如果没有方法论，你可能会写简单的题，手把手的过一遍，但是如果比较难，你就无从下手了。所以，我总结的动态规划的五个部分，用来贯穿整个动态规划系列，就像二叉树系列的递归三部曲和回溯系列的回溯三部曲一样。之后，大家就会逐渐认识到搬家规则五步法的重要性。动态规划法则五步：这里用一个一维的dp数组来保存递归结果1.确定dp数组和下标的意义dp[i]的定义是：第i个的斐波那契值数字是dp[i]2。确定递归公式为什么这是一道非常简单的入门题？因为题目直接给了我们递推公式：状态转移方程dp[i]=dp[i-1]+dp[i-2];3.如何初始化dp数组题目中直接给了我们如何初始化，如下：dp[0]=0;dp[1]=1;4。由递归公式dp[i]=dp[i-1]+dp[i-2]确定遍历顺序；可以看出dp[i]依赖于dp[i-1]和dp[i-2]，那么遍历的顺序一定是从前到后5.dp数组的推导实例根据这个递归公式dp[i]=dp[i-1]+dp[i-2]，我们推导一下，当N为10时，dp数组应该是如下序列：011235813213455如果代码这样写out，发现结果不对，打印出dp数组，看是否和我们导出的序列一致。我们用移动规则的方法完成了上面的分析。C++代码如下：classSolution{public:intfib(intN){if(N<=1)returnN;vectordp(N+1);dp[0]=0;dp[1]=1;for(inti=2;i<=N;i++){dp[i]=dp[i-1]+dp[i-2];}returndp[N];}};时间复杂度：空间复杂度：当然可以发现我们只需要维护两个值，不需要记录整个序列。代码如下：classSolution{public:intfib(intN){if(N<=1)returnN;intdp[2];dp[0]=0;dp[1]=1;for(inti=2;i<=N;i++){intsum=dp[0]+dp[1];dp[0]=dp[1];dp[1]=sum;}returndp[1];}};时间复杂度：空间复杂度：递归求解这道题也可以用递归求解，代码如下：classSolution{public:intfib(intN){if(N<2)returnN;returnfib(N-1)+fib(N-2);}};Timecomplexity:Spacecomplexity:统计编程语言中实现递归的系统栈所占用的空间，通过画树图就可以知道递归的时间复杂度。不清楚的可以看这篇文章：通过一个面试题目，说说递归算法的时间复杂度！总结斐波那契数列是一个非常基础的话题。后面动态规划的讲解中会多次提到斐波那契数列！这里我严格遵循动态规划，这个你应该知道！来分析这个话题。有些分析步骤可能会觉得没必要弄得那么复杂。代码其实是可以推出来的。不过我还是强调一下，简单的题是用来掌握方法论的，动态规划的五个部分会在接下来的动态规划讲解中起到重要作用，敬请期待！您可以通过以下二维码关注。转载本文请联系CodeCaprice公众号。