【Hot100】LeetCode—198. 打家劫舍

题目

• 原题连接：198. 打家劫舍

1- 思路

思路

• 难点 ——> 当前房间偷还是不偷 ？ 状态来源：当前房间偷 or 不偷
  • 偷当前房间 i ： 偷 i ——> dp[i-2] +nums[i]
  • 不偷当前房间 i ： 不偷 i ——> dp[i-1]

2- 实现

⭐198. 打家劫舍——题解思路

class Solution {
    public int rob(int[] nums) {
        if(nums==null && nums.length==0) return 0;
        if(nums.length == 1 ) return nums[0];
        // 1. 定义递推公式
        int[] dp = new int[nums.length];

        // 2. 递推数组
        // dp = Math.max(dp[i-2]+nums[i],dp[i-1]);

        // 3. 初始化
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);

        // 4. 遍历顺序
        for(int i = 2 ; i < nums.length ; i++){
            dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
        }

        return dp[nums.length-1];
    }
}

3- ACM 实现

public class hitHome {


    public static int rob(int[] nums){
        // 1.定义 dp数组
        int[] dp = new int[nums.length];

        // 2. 递推公式
        // dp = Math.max(dp[i-2]+nums[i],dp[i-1]);

        // 3.初始化
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);

        // 4. 遍历顺序
        for (int i = 2 ; i < nums.length;i++){
            dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.length-1];
    }

    public static void main(String[] args) {
        System.out.println("输入数组长度");
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];

        for(int i = 0 ; i < n ; i ++){
            nums[i] = sc.nextInt();
        }
        System.out.println("结果是"+rob(nums));
    }
}