leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0070.cpp (583B)

      1 // memorization approach
      2 class Solution {
      3   public:
      4     int climbStairs(int n) {
      5         vector<int> vec(46);
      6         vec[0] = 1;
      7         vec[1] = 1;
      8         for (int i = 2; i <= n; i++)
      9             vec[i] = vec[i - 1] + vec[i - 2];
     10 
     11         return vec[n];
     12     }
     13 }
     14 
     15 // optimized, memorize only the previous two values
     16 class Solution {
     17   public:
     18     int climbStairs(int n) {
     19         int first = 1, second = 1;
     20         for (int i = 2; i <= n; i++) {
     21             int cnt = first + second;
     22             first = second;
     23             second = cnt;
     24         }
     25 
     26         return second;
     27     }
     28 };