递推式为dp[i] = dp[i - 1] + dp[i - 2],可以递归(重复计算占用大量时间空间,可能超时),也可以建立dp数组,但是观察递推式可以发现当前值只与前两次的值有关,所以可以将dp数组缩减为三个变量。
class Solution { public: int Fibonacci(int n) { if (n == 1 || n == 2) return 1; int n1 = 1, n2 = 1, n3; for (int i = 3; i <= n; i++) { n3 = n1 + n2; n1 = n2; n2 = n3; } return n3; } };