Leetcode 198 - House Robber

題目

Problem#

給你一個整數陣列 M[i] 代表 第 $i$ 間房子的價值，你今天是小偷要去偷錢，但是有個限制是不能連續偷(偷第 $i$ 間，第 $i-1$ 和 $i+1$ 都不能偷)，否則會被抓到，問你最大能偷多少?

想法#

對於 $1$ 到 $i$ 能偷的總價值，假如你挑了第 $i$ 間房子，那一定是和第 $i-2$ 間的房子加總起來($W[i]+W[i-2]$)；如果不挑 $i$ 那必定是 $i-1$ ($W[i-1]$)，而要求兩者最大，所以取 max

W[1...3] = 
             挑自己      不挑自己
dp(2) = max(M[2]+M[2-2], M[2-1])

dp[i] = (1, i) 能搶得最大金額

從左建到右(bottom-up)，保證後面(dp[i])的一定是最大的，因為左邊的 dp[i-1] 或是 dp[i-2] 也已經是最大的

• 時間複雜度: $\mathcal{O}(n)$
• 空間複雜度: $\mathcal{O}(n)$

AC Code#

• Buttom up

Copy

#define N 400
class Solution {
public:
    int n;
    int W[N+5] = {0};
    
    // buttom-up
    int dp[N+5];
    void build()
    {
        dp[0] = 0; // = W[0]
        dp[1] = W[1];
        for(int i = 2; i <= n; i++)
        {
            dp[i] = max(dp[i-2]+W[i], dp[i-1]);
        }
    }
 
    int rob(vector<int>& nums)
    {
        n = nums.size();
        copy(nums.begin(), nums.end(), W+1);
        build();
        return dp[n];
    }
};

view raw leetcode/198_a.cpp delivered with ❤ by emgithub

• Top down

Copy

#define N 400
class Solution {
public:
    int n;
    int W[N+5] = {0};
    // top-down
    int dp[N+5];
    int solve(int i)
    {
        if(i == 0 || i == 1)
            return W[i];
        if(dp[i] != -1)
            return dp[i];
        return dp[i] = max(W[i] + solve(i-2), solve(i-1));
    }
 
    int rob(vector<int>& nums)
    {
        n = nums.size();
        copy(nums.begin(), nums.end(), W+1);
        memset(dp, 0xff, sizeof(dp));
        return solve(n);
    }
};

view raw leetcode/198_b.cpp delivered with ❤ by emgithub