C++ solution inspired by House Robber problem, with comments


  • 0
    A
    class Solution {
    public:
        int rob(vector<int>& nums) {
            int n = nums.size();
            if (n <= 0)
                return 0;
            if (n == 1)
                return nums[0];
            if (n == 2)
                return max(nums[0],nums[1]);
            if (n == 3) {
                int temp = max(nums[0], nums[1]);
                return max(temp, nums[2]);
            }
            // For nums with more than 1 elements
            // If nums[0] is used, calculate max value of 2~(n-2), then add nums[0]
            int dp1[n-2] = {0,nums[2]}; // dp1[i]: max value of the first i houses. dp1[0]=0, dp1[1] = nums[2]
            for (int i=2;i<=(n-3);i++)
                dp1[i] = max(dp1[i-1],dp1[i-2]+nums[i+1]);
            int result_with_0 = dp1[n-3] + nums[0];
            // If nums[0] is no used, calculate max value of 1~(n-1)
            int dp2[n] = {0,nums[1]}; // dp2[0]=0, dp2[1]=nums[1]
            for (int i=2;i<=n-1;i++)
                dp2[i] = max(dp2[i-1],dp2[i-2]+nums[i]);
            int result_without_0 = dp2[n-1];
            return max(result_with_0, result_without_0);
        }
    };

Log in to reply
 

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