给我分析一下打家劫舍这道动态规划题,通俗易懂一些 java
时间: 2023-06-28 10:12:10 浏览: 70
打家劫舍是一道经典的动态规划问题,题目描述如下:
你是一个专业的小偷,计划偷窃沿街的房屋。每间房屋都藏有一定的财物,唯一的限制条件是:相邻的房屋装有相互连通的防盗系统,如果相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你不触动警报装置的情况下,能够偷窃到的最高金额。
例如,输入 [1,2,3,1],输出 4(即偷窃第一间和第三间房屋);输入 [2,7,9,3,1],输出 12(即偷窃第一间、第三间和第五间房屋)。
我们可以使用动态规划来解决这个问题。首先定义一个数组 dp,其中 dp[i] 表示偷取前 i 个房屋所能获得的最大收益。
对于每个房屋 i,有两种情况:
1. 偷取第 i 个房屋,那么此时的最大收益为 dp[i-2] + nums[i],因为不能偷取相邻房屋,所以要跳过 i-1 号房屋。
2. 不偷取第 i 个房屋,那么此时的最大收益为 dp[i-1]。
因此,我们可以得到状态转移方程:
dp[i] = max(dp[i-2] + nums[i], dp[i-1])
最终的答案即为 dp[n-1],其中 n 是数组的长度。
下面是 Java 代码实现:
```java
public int rob(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
if (n == 1) {
return nums[0];
}
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
}
return dp[n-1];
}
```