My DP solution with 1-dimensional array


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

Log in to reply
 

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