198.打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

思路

  • 本质上就是加不加上当前值的问题
  • 只不过初始值dp[0],dp[1]需要分析
  • dp[1]表示对第二间房子偷不偷，那么就是要么偷第一间，要么偷第二间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package com.wereash.scut_hot100.dp;

import java.util.Scanner;

/**
 * @Author: WereAsh
 * @Date:2026-02-09 21:19
 **/
public class Solution198 {
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        String[] str=scanner.nextLine().split(",");
        int n=str.length;
        if(n==1) {
            System.out.println(str[0]);
        }
        if(n==2) {
            System.out.println(Math.max(Integer.parseInt(str[0]),Integer.parseInt(str[1])));
        }
        int[] nums=new int[n];
        for (int i = 0; i < n; i++) {
            nums[i]=Integer.parseInt(str[i]);
        }
        int[] dp=new int[n];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[1],nums[0]);
        for(int i=2;i<n;i++){
            dp[i]=Math.max(dp[i-1],nums[i]+dp[i-2]);
        }
        System.out.println("最大可偷取的金额为:"+dp[n-1]);
    }
}