【Hot100】LeetCode—198. 打家劫舍

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

1- 思路

动规五部曲

• 1- 定义 dp 数组
  • int[] dp = new int[nums.length]
  • dp[i] 代表考虑下标i 偷的最大金币数
• 2- 递推公式
  • 当偷 i ： dp[i-2] + nums[i]
  • 当不偷 i ： dp[i-1]
  • 结论：dp[i] = Math.max(dp[i],dp[i-1])
• 3- 初始化
  • dp[0] = nums[0];
  • dp[1] = Math.max(nums[0],nums[1]);
• 4- 遍历顺序
  • i 从 2 开始遍历

2- 实现

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

class Solution {
        public int rob(int[] nums) {
        
        // 1.定义 dp 确定含义
        // dp[i] 代表，遍历到 i 的最大金币数
        int len = nums.length;
        if(len==1){
            return nums[0];
        }
        int[] dp = new int[len];

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

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

        for(int i = 2 ; i < len;i++){
            dp[i] = Math.max(dp[i-1] , dp[i-2] + nums[i]);
        }
        return dp[len-1];
    }
}

3- ACM 实现

public class rob {


    public static int rob(int[] nums){

        // 1. 定义 dp 数组
        // dp[i] 代表 第 i 天获得的最大金币数
        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }
        int[] dp = new int[len];

        // 2. 递推公式
        // i 偷 dp[i-2] + nums[i]
        // i 不偷 dp[i-1]
        // dp[i] = 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 < len; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        return dp[len - 1];
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        String[] parts = input.split(" ");
        int[] nums = new int[parts.length];
        for(int i = 0 ; i < parts.length;i++){
            nums[i] = Integer.parseInt(parts[i]);
        }
        System.out.println("结果是"+rob(nums));
    }
}