Share my C++ solution using dynamic programming


  • 0
    V
    class Solution {
    public:
        int rob(vector<int>& nums) {
            int n = nums.size();
            if (n == 0) return 0;
            if (n == 1) return nums[0];
            
            vector<int> dpMoney(n, 0);
            dpMoney[0] = nums[0];
            dpMoney[1] = max(nums[0], nums[1]);
            
            int i = 0;
            for (i = 2; i < n; i++)
                dpMoney[i] = max(nums[i] + dpMoney[i-2], dpMoney[i-1]);
                
            return dpMoney[n-1];
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.