4-lines DP in-place O(n) solution in Java


  • 2
    S

    Hi guys!

    The idea is to use the input array as an array for DP. In each step we choose the maximum one of to options: rob current house

    num[i-2] + num[i]

    or not rob current house

    num[i-1].


    public class Solution {
        public int rob(int[] num) {
            if (num.length > 1) num[1] = Math.max(num[0], num[1]);
            for (int i = 2; i < num.length; i++)
                num[i] = Math.max(num[i-2] + num[i], num[i-1]);
            return num.length == 0 ? 0 : num[num.length-1];
        }
    }

  • 0
    J

    Nice. Translated into C here. 1ms.

    int rob(int* nums, int numsSize) {
        if ((numsSize) == 0) { return 0; }
        if (numsSize > 1) {
            if (nums[0] > nums[1]) {
                nums[1] = nums[0];
            }
        }
        for (int i = 2; i < numsSize; i++) {
            if (nums[i] + nums[i-2] > nums[i-1]) {
                nums[i] = nums[i] + nums[i-2];
            } else {
                nums[i] = nums[i-1];
            }
        }
        return nums[numsSize-1];
    }
    

Log in to reply
 

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