leetcode

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

0509.cpp (545B)

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