【Hot100】LeetCode—198. 打家劫舍

目录

• 题目
• 1- 思路
• 2- 实现
• • ⭐198. 打家劫舍——题解思路
• 3- ACM 实现

题目

• 原题连接：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));     } }