問題的鏈接在這里：House Robber II
我已經使用下面的代碼解決了House Robber，它是絕對正確的：
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];
}
}
因此，我認為解決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];
}
}
誰能告訴我為什么上面的代碼不能解決這個問題？它的盲點是什么？請幫我改正。謝謝！
uj5u.com熱心網友回復：
我發現了你的錯誤。
在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];
}
}
你solve從范圍呼叫[0, n-2]到[1, n-1]。但是，您的回圈從end - 1. 這意味著您有效地在[0, n-3]和上運行動態編程[1, n-2]，這不會給您正確的答案。
嘗試更改end - 1為end. 或者，您可以更改：
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));
但是請注意，如果您同時進行了兩項更改，它將再次不正確。
uj5u.com熱心網友回復：
感謝@Ryan Zhang！在我將代碼更改為下面之后。我可以解決這個問題。
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];
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/492028.html