跳台阶

上n层楼梯，最后一步要不就是上1层，要不就是上两层，所以上n层楼梯的方法数量就等于最后跳一层也就是上n-1层台阶的方法数量加上最后跳两层也就是上n-2层台阶的方法数量。

  1. class Solution {
  2. public:
  3.     // 1 递归 斐波那契数列 f(n) = f(n-1) + f(n-2)
  4.     // 2 数组代替栈保存中间结果
  5.     // 3 滑动数组代替栈保存中间结果
  6.     int numWays(int n) {
  7.         if (n == 0) return 1;
  8.         if (n <= 2) return n;
  9.         int num1 = 1, num2 = 2, res = 0;
  10.         while (n-- > 2)
  11.         {
  12.             res = (num1 + num2) % int(1e9+7);
  13.             num1 = num2;
  14.             num2 = res;
  15.         }
  16.         return res;
  17.     }
  18. };

斐波那契数列

  1. #include <iostream>
  2. #include <vector>
  4. using namespace std;
  5. vector<int> fseq(int n) {
  6.     vector<int> res(n);
  7.     res[0] = 0;
  8.     res[1] = 1;
  9.     for (int i = 2; i < n; i++) {
  10.         res[i] = res[i-1] + res[i-2];
  11.     }
  12.     return res;
  13. }
  15. int main(int argc, char *argv[]) {
  16.     vector<int> res(fseq(10));
  17.     for (int n : res) cout << n << ' ';
  18.     cout << endl;
  20.     return 0;
  21. }