[LeetCode 笔记] 198. House Robber

前言

　　这题是一题动态规划问题，目标是撷取不连续的元素，全部相加起来选出最优解，因只用了一层迴圈，时间複杂度可估 O(n)，这里有 JAVA 和 Python 的写法。

题目

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

你是一个专业的小偷，计画了抢劫街道上的房子，每个房子藏有一定数量的钱，阻止你的唯一条件是房子之间有相连的安全系统，如果相连的房子同一晚被闯入，就会通知警方。

给定一个整数阵列 nums 代表每一间房子的金额，回传撷取最高的金额且没有惊动警察。

题目连结：https://leetcode.com/problems/house-robber/

题目限制

1 <= nums.length <= 100
0 <= nums[i] <= 400

範例

Input: nums = [1,2,3,1]Output: 4Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).Total amount you can rob = 1 + 3 = 4.

Input: nums = [2,7,9,3,1]Output: 12Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).Total amount you can rob = 2 + 9 + 1 = 12.

思路&笔记

撷取不连续的元素，全部相加起来，这归类在动态规划的想法，是利用先前的计算结果来推导目前的最优解。我们将两个变数 rob 和 notrob，分别表示如果抢当前房屋和不抢当前房屋时，能够得到的最大金额。在遍历每个房屋时，透过更新这两个变数，计算出最终的最大金额。

JAVA 实现

public int rob(int[] num) {    int rob = 0; // 抢当前的房子的最大金额    int notrob = 0; // 不抢当前的房子的最大金额    for(int i=0; i<nums.length; i++) {        int currob = notrob + nums[i]; // 0 + 当前房子 (如果抢了当前房子就不能抢前一个房子)        notrob = Math.max(notrob, rob); // 不抢当前的房子和抢当前的房子比较 (因为在不抢目前房屋的情况下，可以选择抢或不抢上一个房屋，所以要取最大值)        rob = currob; // 抢当前的房子的最大金额    }    return Math.max(rob, notrob); // 最后选出最大的金额}

Python 实现

使用了和 Java 一样的逻辑执行，换成 Python 的写法。

class Solution:    def rob(self, nums: List[int]) -> int:                rob = 0        not_rob = 0        for num in nums:            cur_rob = not_rob + num            not_rob, rob = max(not_rob, rob), cur_rob        return max(rob, not_rob)

成绩

LanguageRuntimeMemoryJava0ms40.62MBPython48ms16.33MB

(新手上路，如有错误请友善告知，感谢)

Blog
https://chris81051.github.io/2023/11/14/LeetCode-198-House-Robber-Java-Python/
有分享技术文章、科技新闻、日常生活，欢迎一起讨论