打家劫舍完整代码java
时间: 2023-12-17 19:28:23 浏览: 32
以下是打家劫舍问题的完整Java代码:
```java
class Solution {
public int rob(int[] nums) {
int len = nums.length;
if (len == 1) {
return nums[0];
} else if (len == 2) {
return Math.max(nums[0], nums[1]);
} else {
// 不偷第一家
int[] dp1 = new int[len];
dp1[1] = nums[1];
for (int i = 2; i < len; i++) {
dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i]);
}
// 不偷最后一家
int[] dp2 = new int[len];
dp2[0] = nums[0];
dp2[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < len - 1; i++) {
dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i]);
}
return Math.max(dp1[len - 1], dp2[len - 2]);
}
}
}
```
该代码实现了打家劫舍问题的解决方案,包括了房子是环型的情况。其中,使用了动态规划的思想,通过计算偷和不偷两种情况下的最大价值,来得到最终的结果。
--相关问题--:
1. 动态规划在解决什么问题时比较有效?
2. 除了动态规划,还有哪些常用的算法思想?
3.