打家劫舍问题

2023-06-12 50

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 打家劫舍问题

题目

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

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

实例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 中其他内容

当前金额是由（前一个的金额）或（当前金额加上除前一个金额外最大的金额）中大的那个构成

过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);
    }
}