algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

house-robber.cpp (845B)


      1 class Solution {
      2 public:
      3 
      4     int getBest(int idx, vector<int>& nums, vector<int>& best) {
      5         
      6         if(idx >= nums.size()) {
      7             return 0;
      8         }
      9 
     10         if(best[idx] != -1) {
     11             return best[idx];
     12         }
     13 
     14         int nextBest = getBest(idx+1, nums,best);
     15         int p1Best = getBest(idx+2, nums,best);
     16         int cur = std::max(nextBest, p1Best + nums[idx]);
     17         best[idx] = cur;
     18 
     19         return cur;
     20     }
     21     int rob(vector<int>& nums) {
     22         // ideas:
     23             // greedy? x
     24             // dp?
     25                 // recurse
     26                     // from the end:
     27                         // best is to take current
     28                             // compare current best with next best and set it as such
     29         vector<int> best = vector<int>(nums.size(), -1);
     30         return getBest(0,nums, best);
     31     }
     32 };