LeetCode509：斐波那契数列
代码如下
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数组转移，然后占据较大空间来减少时间复杂度。