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 };