网站建设手机站谷歌seo服务商

代码如下

class Solution {
public:int fib(int n) {//这个是为了特殊n，当n = 0时， 当 n = 1时。if(n == 0)  return 0;if(n == 1)  return 1;//第一次开dp专题，连dp数组都忘记定义了。只写了下面，哭vector<int> dp(n + 1, 0);dp[0] = 0;dp[1] = 1; //dp转移状态方程for(int i = 2; i < n + 1; i++){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};

        实际上我代码里面都是我要讲的东西了，同学们很多时候编写斐波那契，就喜欢按照正常的编写或者递归，实际上这两种都可以，但是有些时候题目要求限制时间的话，那就只能以空间换时间，动态规划的本质就是，把之前的求的数据存到dp数组中，后面可以用dp数组转移，然后占据较大空间来减少时间复杂度。