LeetCode question : House Robber II The code does not return correct output-CodePudding

The link to the question is here : House Robber II

I've solved House Robber using the code below and it is absolutely correct:

class Solution {
    public int rob(int[] nums) {
        int[] dp = new int[nums.length   2];
        for(int i = nums.length - 1; i >= 0; i--){
            dp[i] = Math.max(dp[i   1], nums[i]   dp[i   2]);
        }
        return dp[0];
   }
}

Therefore, I thought all I need do to solve the House Robber II is to change my code into below:

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 1) return nums[0];
        if(n == 2) return Math.max(nums[0], nums[1]);
        // Since the house can not be both the first and the last, I change the range that could possible be robbed. The first range is the first house till the second last house and the second range is the second house till the last house.
        return Math.max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));
    }
    public int solve(int[] nums, int start, int end){
        int[] dp = new int[end   2];
        for(int i = end - 1; i >= start; i--){
            dp[i] = Math.max(dp[i   1], nums[i]   dp[i   2]);
        }
        return dp[start];
    }
}

Can anyone tell me why this question can not be solved by the code above? What is the blind spot of it? Please help me correct it. Thanks!

CodePudding user response：

I have found your error.

In this code for House Robber II:

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 1) return nums[0];
        if(n == 2) return Math.max(nums[0], nums[1]);
        // Since the house can not be both the first and the last, I change the range that could possible be robbed. The first range is the first house till the second last house and the second range is the second house till the last house.
        return Math.max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));
    }
    public int solve(int[] nums, int start, int end){
        int[] dp = new int[end   2];
        for(int i = end - 1; i >= start; i--){
            dp[i] = Math.max(dp[i   1], nums[i]   dp[i   2]);
        }
        return dp[start];
    }
}

You call solve from the range [0, n-2] to [1, n-1]. However, your loop starts from end - 1. This means that you are effectively running dynamic programming over [0, n-3] and [1, n-2], which will not give you the correct answer.

Try changing end - 1 to end. Alternatively, you can change:

return Math.max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));

return Math.max(solve(nums, 0, n - 1), solve(nums, 1, n));

Notice, however, that if you make both changes it will be incorrect again.

CodePudding user response：

Thanks to @Ryan Zhang ! After I changed my code to below. I can solve this question.

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 1) return nums[0];
        if(n == 2) return Math.max(nums[0], nums[1]);
        return Math.max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));
    }
    public int solve(int[] nums, int start, int end){
        int[] dp = new int[nums.length   2];
        for(int i = end; i >= start; i--){
            dp[i] = Math.max(dp[i   1], nums[i]   dp[i   2]);
        }
        return dp[start];
    }
}