给定一个数组 arr[]，代表呈圆形排列的房子，其中每个房子都有一定的价值。一个小偷希望最大化偷窃的总价值，但不能偷窃两个相邻的房子。由于房子是围成一圈的，因此第一栋和最后一栋房子也被视为相邻。请确定小偷可以偷窃的最大金额。
示例：
> 输入： arr[] = [2, 2, 3, 1, 2]
> 输出： 5
> 解释： 最大偷窃价值：arr[0] + arr[2] = 2 + 3 = 5 或 arr[2] + arr[4] = 3 + 2 = 5。
>
> 输入： arr[] = [2, 3, 2]
> 输出： 3
> 解释： arr[0] 和 arr[2] 不能同时被偷，因为它们是相邻的房子。
目录
- [朴素方法] 使用递归 – O(2^n) 时间和 O(n) 空间
- [进阶方法 – 1] 使用 自顶向下 DP（记忆化） – O(n) 时间和 O(n) 空间
- [进阶方法 – 2] 使用 自底向上 DP（制表） – O(n) 时间和 O(n) 空间
- [期望方法] 使用空间优化的 DP – O(n) 时间和 O(1) 空间
[朴素方法] 使用递归 – O(2^n) 时间和 O(n) 空间
> 这个问题的核心思路在于处理环形的约束条件，即第一栋和最后一栋房子是相邻的。
>
> 为了避免同时偷窃这两栋房子，我们将问题转化为两种线性情况来处理：
>
> – 考虑从索引 0 到 n−2 的房子（排除最后一栋房子）。
> – 考虑从索引 1 到 n−1 的房子（排除第一栋房子）。
>
> 对于每种情况，小偷在每一栋房子面前都有两个选择：
>
> – 偷当前房子 -> 然后必须跳过相邻的（前一栋）房子，并加上当前房子的价值。
> – 不偷当前房子 -> 则保留到目前为止获得的最大价值。
>
> 我们分别使用递归求解这两种情况，然后取两个结果中的最大值。
C++
//Driver Code Starts
#include
#include
using namespace std;
//Driver Code Ends
// Calculate the maximum stolen value recursively
int maxValRec(vector &arr, int i, int j) {
// If no houses are left, return 0.
if (i> j) return 0;
// If only 1 house is left, rob it.
if (i == j) return arr[i];
// Two Choices:
// Rob the jth house and skip the (j-1)th house
int pick = arr[j] + maxValRec(arr, i, j-2);
// Skip the jth house
int notPick = maxValRec(arr, i, j-1);
// Return the max of two choices
return max(pick, notPick);
}
// Function to calculate the maximum stolen value
int maxValue(vector& arr) {
int n = arr.size();
int ans = 0;
// Skip the last house
ans = max(ans, maxValRec(arr, 0, n-2));
// Skip the first house
ans = max(ans, maxValRec(arr, 1, n-1));
return ans;
}
//Driver Code Starts
int main() {
vector arr = {2, 2, 3, 1, 2};
cout << maxValue(arr);
return 0;
}
//Driver Code Ends
Java
//Driver Code Starts
class GfG {
//Driver Code Ends
// Calculate the maximum stolen value recursively
static int maxValRec(int[] arr, int i, int j) {
// If no houses are left, return 0.
if (i > j) return 0;
// If only 1 house is left, rob it.
if (i == j) return arr[i];
// Two Choices:
// Rob the jth house and skip the (j-1)th house
int pick = arr[j] + maxValRec(arr, i, j - 2);
// Skip the jth house
int notPick = maxValRec(arr, i, j - 1);
// Return the max of two choices
return Math.max(pick, notPick);
}
// Function to calculate the maximum stolen value
static int maxValue(int[] arr) {
int n = arr.length;
int ans = 0;
// Skip the last house
ans = Math.max(ans, maxValRec(arr, 0, n - 2));
// Skip the first house
ans = Math.max(ans, maxValRec(arr, 1, n - 1));
return ans;
}
//Driver Code Starts
public static void main(String[] args) {
int[] arr = {2, 2, 3, 1, 2};
System.out.println(maxValue(arr));
}
}
//Driver Code Ends
Python
# Calculate the maximum stolen value recursively
def maxValRec(arr, i, j):
# If no houses are left, return 0.
if i > j:
return 0
# If only 1 house is left, rob it.
if i == j:
return arr[i]
# Two Choices:
# Rob the jth house and skip the (j-1)th house
pick = arr[j] + maxValRec(arr, i, j - 2)
# Skip the jth house
notPick = maxValRec(arr, i, j - 1)
# Return the max of two choices
return max(pick, notPick)
# Function to calculate the maximum stolen value
def maxValue(arr):
n = len(arr)
ans = 0
# Skip the last house
ans = max(ans, maxValRec(arr, 0, n - 2))
# Skip the first house
ans = max(ans, maxValRec(arr, 1, n - 1))
return ans
# Driver Code
if __name__ == "__main__":
arr = [2, 2, 3, 1, 2]
print(maxValue(arr))