509. 斐波那契数

509. 斐波那契数斐波那契数通常用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 30动态规划思路class Solution { public: //动态规划思路 int fib(int n) { vectorintdp(n1); dp[0]0; if(n0){ dp[1]1; for(int i2;in;i){ dp[i]dp[i-1]dp[i-2]; } } return dp[n]; } };还可以用递推做这里就不做代码结束了