打家劫舍问题

绝地灬酷狼 2024-03-30 15:16 23阅读 0赞

## 力扣（LeetCode）198.打家劫舍【中等】【dp动态规划】 ##

`记录一道关于dp的题目，题目本身不难，主要是学习一下思想~`  
题目地址： [（LeetCode）198.打家劫舍][LeetCode_198.]

--------------------

#### 文章目录 ####

*  力扣（LeetCode）198.打家劫舍【中等】【dp动态规划】
 *  题目
 *  解题思路
 *  总结

--------------------

## 题目 ##

> 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。  
> 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

> 实例1：  
> 输入：\[1,2,3,1\]  
> 输出：4  
> 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。  
> 偷窃到的最高金额 = 1 + 3 = 4 。

> 实例2：  
> 输入：\[2,7,9,3,1\]  
> 输出：12  
> 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。  
> 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

> 提示：  
> 1 <= nums.length <= 100  
> 0 <= nums\[i\] <= 400

## 解题思路 ##

> 如果你是初次接触动态规划的问题，你只需要牢记一句话：“当前的结果都是由之前的过程推导出来的。”而不可以是先考虑后面的情况，因为后面的情况是未知的，我们只知道前面的结果，用已知求未知是关键。

> ①要把推导的过程列出来，从而知道当前结果是怎么推导出来的（画表格），  
> ②根据表格规律，进而写出递推方程式  
> ③找出base情况(即dp \[i\] 的基础情况,这道题的base情况就是数组中每个元素本身)  
> ④根据方程式计算出 dp 中其他内容

当前金额是由（前一个的金额）或（当前金额加上除前一个金额外最大的金额）中大的那个构成  
![在这里插入图片描述][ea94c5f3554e4bbd9f475cf827e5ea92.png]

> 过leetcode代码如下（Java）：

class Solution {
        
        public int rob(int[] num){
        
            int []dp = new int[num.length];
    //      递推方程：dp[i] = max(dp[i-1] , dp[i]+max(dp[i-2]~dp[0]))
            for (int i = 0; i < num.length; i++) {
        
                dp[i] = num[i];
            }
            for (int i = 1; i < dp.length; i++) {
        
                int max = 0;
                for (int j = i - 2; j >= 0; j--) {
        
                    if (dp[j] > max)
                        max = dp[j];
                }
                dp[i] = Math.max(dp[i - 1], dp[i] + max);
            }
            int max = 0;
            for (int j : dp) {
        
                if (j > max)
                    max = j;
            }
            return max;
        }
    }

> 过lanqiao代码如下（Java）：

import java.util.Scanner;
    
    public class Main {
        
        static int[] dp;
    
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            String line = scanner.nextLine();
            line = line.substring(1, line.length() - 1);
            String[] array = line.split(",");
            dp = new int[array.length];
    //      递推方程：dp[i] = max(dp[i-1] , dp[i]+max(dp[i-2]~dp[0]))
            for (int i = 0; i < array.length; i++) {
        
                dp[i] = Integer.parseInt(array[i]);
            }
            for (int i = 1; i < dp.length; i++) {
        
                int max = 0;
                for (int j = i - 2; j >= 0; j--) {
        
                    if (dp[j] > max)
                        max = dp[j];
                }
                dp[i] = Math.max(dp[i - 1], dp[i] + max);
            }
            int max = 0;
            for (int j : dp) {
        
                if (j > max)
                    max = j;
            }
            System.out.println(max);
        }
    }

--------------------

## 总结 ##

`当我们初次接触到dp问题时，总是以最直观的方法进行求解，即先思考后面的情况如何规划，却没有想到后面的情况是不可预知的；应该仔细分析已知条件，从前面已知的条件入手，推导出当前这项的最优解，这也是动态规划的核心！`

文章粗浅，希望对大家有帮助！

[LeetCode_198.]: https://leetcode.cn/problems/house-robber/
[ea94c5f3554e4bbd9f475cf827e5ea92.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/fbc9d6a0c93643c6af2d6bc9152941bc.png