Chris's Lab

If you obey all the rules,you miss all the fun.

0%

[LeetCode] 198. House Robber

發表於 分類於 ， ， Disqus：
這題是一題動態規劃問題，目標是擷取不連續的元素，全部相加起來選出最優解

前言

　　這題是一題動態規劃問題，目標是擷取不連續的元素，全部相加起來選出最優解，因只用了一層迴圈，時間複雜度可估 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

範例

1
2
3
4
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
1
2
3
4
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: 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 實現

1
2
3
4
5
6
7
8
9
10
11
12
13
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 的寫法。

1
2
3
4
5
6
7
8
9
10
11
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)

成績

Language Runtime Memory
Java 0ms 40.62MB
Python 48ms 16.33MB