leetcode

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

1137.cpp (650B)

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