509. 斐波那契数
思路:
运用动态规划的思想
1,先定义一个数组
2,初始化
3,递推公式
4,遍历
代码:
1 int fib(int n) 2 { 3 if (n == 0) return 0; 4 if (n == 1) return 1; 5 6 vector<int> selected(n+1); 7 selected[0] = 0; 8 selected[1] = 1; 9 10 for (int i = 2; i <= n; i++) 11 { 12 selected[i] = selected[i - 1] + selected[i - 2]; 13 } 14 15 return selected.back(); 16 }