2025年- H80-Lc188--198.打家劫舍(动态规划）--Java版

1.题目描述

2.思路

(1)首先只有一个房间的时候，dp[0]=nums[0].
(2)如果有两个房间的时候，dp[i]=math.max（nums[0],nums[i])。
(3)因为前两个元素已经初始化了，所以i从2开始遍历，遍历到最后一个元素nums.size()-1。
(4)如果偷最后一个房间，则收获的最大钱币数dp[i-2]+dp[i]。如果不偷最后一个房间，则收获的最大钱币数dp[i-1].
考虑头两个元素的状态，和最后一个元素的状态

3.代码实现

public class H198 {public int rob(int[] nums) {if(nums.length==0||nums==null){return 0;}if(nums.length==1){return nums[0];}int n=nums.length;int[] dp=new int[n];//如果只有一家dp[0]=nums[0];dp[1]=Math.max(nums[0],nums[1]);for(int i=2;i<n;i++){//如果i代表最后一家，如果最后一家我们偷的话，金钱的数额必定有nums[i],而且不能偷相邻的，所以要递归遍历dp[i-2]//如果i代表最后一家不偷的话，那么就递归遍历dp[i-1]中最大的金钱数量。dp[i]=Math.max(nums[i]+dp[i-2],dp[i-1]);}//最后返回dp得到的结果return dp[n-1];}public static void main(String[] args){H198 test=new H198();int[] nums={1,2,3,1};int res=test.rob(nums);System.out.print(res);}}