[LeetCode] 198. House Robber* 解題思路 (Easy)

這題需要跨陣列 index 數字相加，也就是數字不能相鄰。

LeetCode 題目連結

 

https://leetcode.com/problems/house-robber/

題目

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 system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

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.

Example 2:

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.

Constraints:

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

Accept 作法

這題是動態規劃 DP 問題，時間複雜度 O(n)，原本誤以為是要奇數或是偶數最大總和，結果不是，真的是陷阱題，要好好看題目。


Runtime: 0 ms
Memory: 36.8 MB

Java 程式碼

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        
        if(nums.length ==1){
            return nums[0];
        }
        int odd = 0;
        int even = 0;
        
        for(int i =0; i<nums.length;i++){
            if(i % 2 == 0){
               even = Math.max(even + nums[i], odd); 
            }else{
                odd =  Math.max(even , odd + nums[i]); 
            }
        }
        return  Math.max(even , odd);
    }
}

更多 LeetCode 相關資源

• 從LeetCode學演算法｜基礎篇
• Udemy 暢銷 - Master the Coding Interview: Data Structures + Algorithms

 

複習程式面試書籍

除了 LeetCode 練習外，我也入手了這本，題庫來自真正的面試，並非摘自教科書。它們反映出頂尖公司真正會出的題目，你可以藉此做好充分準備。
需要的話可以看看，寫得很仔細。

⇒ 提升程式設計師的面試力：189道面試題目與解答（第六版）

相關 LeetCode文章一律會放在 程式解題 標籤分類，歡迎持續追蹤。

⇒ 點我看更多程式解題