LeetCode: 198. Robbery dynamic planning solution

You are a professional thief, planning to rob the houses along the street. There is a certain amount of cash hidden in each room, and the only constraint on your ability to steal is that adjoining houses are equipped with interconnected security systems that will automatically alert the police if two houses are broken into on the same night. Given an array of non-negative integers representing the amount of money stored in each house, calculate the maximum amount of money you can steal in one night without setting off the alarm.

Source: LeetCode link: leetcode-cn.com/problems/ho… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Answer:

S1: If the array length is 0, return this element. If the array length is 1, return this element

S2: remember I the biggest element in the element value and for f (I), is (I + 1) = f Max {f (I – 2) + nums [I], f (I – 1)};

The implementation code

public static int rob(int[] nums) {
        return robTwo(nums, nums.length, new int[nums.length]);
    }

    S2: f(I +1) = Max {f(i-2)+nums[I], f(i-1)}; s2: f(I +1) = Max {f(i-2)+nums[I], f(i-1)}; * *@param nums
     * @param n
     * @param memo
     * @return* /
    public static int robTwo(int[] nums, int n, int[] memo) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return nums[0];
        }
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                memo[0] = nums[0]; / / record f (0)
            } else if (i == 1) {
                memo[1] = Math.max(nums[0], nums[1]); / / record f (1)
            } else {
                memo[i] = Math.max(memo[i - 2] + nums[i], memo[i - 1]);
            }
        }
        Arrays.sort(memo); // Take the maximum after sorting
        return memo[n - 1];
    }
Copy the code