aboutsummaryrefslogtreecommitdiffstats
path: root/70/main.cpp
blob: 23f430fcc6d26c1dc26a7a5816c05ff7f0fdc9eb (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include "header.hpp"

class Solution {
public:
  int climbStairs(int n) { return this->lookup[n]; }
  /* static int climbStairs(int n) { */
  /*   if (n == 1) */
  /*     return 1; */
  /*   if (n == 2) */
  /*     return 2; */
  /*   int prev_1 = 2; */
  /*   int prev_2 = 1; */
  /*   int neu = 0; */
  /*   for (int i = 3; i <= n; ++i) { */
  /*     neu = prev_1 + prev_2; */
  /*     prev_2 = prev_1; */
  /*     prev_1 = neu; */
  /*   } */

  /*   return prev_1; */
  /* } */
  std::vector<int64_t> lookup = {
      0,         1,         2,          3,          5,          8,
      13,        21,        34,         55,         89,         144,
      233,       377,       610,        987,        1597,       2584,
      4181,      6765,      10946,      17711,      28657,      46368,
      75025,     121393,    196418,     317811,     514229,     832040,
      1346269,   2178309,   3524578,    5702887,    9227465,    14930352,
      24157817,  39088169,  63245986,   102334155,  165580141,  267914296,
      433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976};

private:
};

int main(int argc, char **argv) {
  Solution *solution = new Solution;
  std::cout << solution->climbStairs(2) << "\n";
  std::cout << solution->climbStairs(3) << "\n";
  std::cout << solution->climbStairs(4) << "\n";
  std::cout << solution->climbStairs(5) << "\n";
  return 0;
}