打家劫舍--动态规划解决JAVA
时间: 2023-08-16 11:13:55 浏览: 55
以下是一个使用动态规划解决打家劫舍问题的Java代码示例:
```java
class Solution {
public int rob(int\[\] nums) {
if(nums.length==1) return nums\[0\];
else if(nums.length==2) return Math.max(nums\[0\],nums\[1\]);
int\[\] dp = new int\[nums.length\];//该容器内元素表示从头号房开始偷到i偷到的最大金额
dp\[0\] = nums\[0\];
dp\[1\] = Math.max(nums\[0\],nums\[1\]);
for(int i=2;i<nums.length;++i){
dp\[i\] = dp\[i-2\] + nums\[i\];
dp\[i\] = Math.max(dp\[i\],dp\[i-1\]);
}
return dp\[nums.length-1\];
}
}
```
这段代码使用了一个动态规划的思路来解决打家劫舍问题。首先,我们定义一个数组`dp`,其中`dp\[i\]`表示从头号房开始偷到第`i`号房的最大金额。然后,我们初始化`dp\[0\]`为第一个房间的金额,`dp\[1\]`为第一个和第二个房间中金额较大的那个。接下来,我们使用一个循环从第三个房间开始遍历,每次更新`dp\[i\]`为`dp\[i-2\]`加上当前房间的金额,然后与`dp\[i-1\]`比较取较大值。最后,返回`dp\[nums.length-1\]`即为偷到的最大金额。
希望对你有帮助!
#### 引用[.reference_title]
- *1* *2* *3* [动态规划----解决“打家劫舍”问题](https://blog.csdn.net/qq_63691275/article/details/126941380)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^control_2,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]