【Leetcode】198. House Robber

題目位址：

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

有一個數組 A A A代表每個房子的财富值。有個小偷想偷盡可能多的财富，但他不能同時偷相鄰的兩個房子。問他最多能偷多少錢。

法1：動态規劃。設 f [ i ] f[i] f[i]代表到第 i i i個房子為止，他能偷的最大财富。設每個房子的财富值為 h [ i ] h[i] h[i]。如果已知到第 i − 1 i-1 i−1個房子為止，他能偷的最大财富值，那麼到第 i i i個房子為止，能偷的最大财富值有兩種情況：

1、他偷第 i i i個房子，那麼最大是 f [ i − 2 ] + h [ i ] f[i-2]+h[i] f[i−2]+h[i]；

2、他不偷第 i i i個房子，那麼最大是 f [ i − 1 ] f[i-1] f[i−1]。

取兩者較大的即可。代碼如下：

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        // dp代表第i棟房子為止，小偷能偷到的最大财富值（i從1開始計算）
        int[] dp = new int[nums.length + 1];
        dp[1] = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            dp[i + 1] = Math.max(nums[i] + dp[i - 1], dp[i]);
        }
        
        return dp[nums.length];
    }
}
           

時空複雜度 O ( n ) O(n) O(n)。

觀察得出，目前的值隻依賴于前兩個位置的值，是以可以用滾動數組的方式優化空間。

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int[] dp = new int[3];
        dp[1] = nums[0];
        // ind記錄目前更新到哪兒了
		int ind = 1;
        for (int i = 1; i < nums.length; i++) {
        	// 滾動一下，然後更新
            ind = (ind + 1) % 3;
            dp[ind] = Math.max(dp[(ind + 1) % 3] + nums[i], dp[(ind + 2) % 3]);
        }
        
        return dp[ind];
    }
}
           

時間複雜度不變，空間 O ( 1 ) O(1) O(1)。

法2：狀态機（本質上其實還是動态規劃）。下面用圖論的語言來叙述這個問題。考慮一個兩個頂點的圖 G G G，兩個頂點分别為 v 1 v_1 v1​和 v 2 v_2 v2​，其中 v 1 v_1 v1​表示“最後一個房屋要選”這個狀态， v 2 v_2 v2​表示“最後一個房屋不選”這個狀态。那麼，存在的有向邊就是 ( v 0 , v 0 ) (v_0,v_0) (v0​,v0​)， ( v 0 , v 1 ) (v_0,v_1) (v0​,v1​)和 ( v 1 , v 0 ) (v_1,v_0) (v1​,v0​)，因為如果某個房子不選，那麼下一個房子可以選或者不選；而某個房子選了，下一個房子就不能選。是以整個題目就相當于，在這個圖上走 n n n步，所能得到的最大收益是多少（注意這裡和圖論裡的邊權并不一樣，這裡的邊權是跟走的步數相關的，并不是個确定值）。設 f [ i ] [ 0 ] f[i][0] f[i][0]表示走了 i i i步停留在 v 0 v_0 v0​時獲得的最大收益， f [ i ] [ 1 ] f[i][1] f[i][1]表示走了 i i i步停留在 v 1 v_1 v1​時獲得的最大收益。那麼就有： { f [ i ] [ 0 ] = max ⁡ { f [ i − 1 ] [ 0 ] , f [ i − 1 ] [ 1 ] } f [ i ] [ 1 ] = f [ i − 1 ] [ 0 ] + A [ i ] \begin{cases}f[i][0]=\max\{f[i-1][0],f[i-1][1]\}\\f[i][1]=f[i-1][0] +A[i] \end{cases} {f[i][0]=max{f[i−1][0],f[i−1][1]}f[i][1]=f[i−1][0]+A[i]​最後要傳回的結果就是 max ⁡ { f [ n ] [ 0 ] , f [ n ] [ 1 ] } \max\{f[n][0],f[n][1]\} max{f[n][0],f[n][1]}。其中 f [ 0 ] [ 0 ] = 0 , f [ 0 ] [ 1 ] = A [ 0 ] f[0][0]=0,f[0][1]=A[0] f[0][0]=0,f[0][1]=A[0]。代碼如下：

public class Solution {
    public int rob(int[] nums) {
    	if (nums == null || nums.length == 0) {
    		return 0;
    	}
    	
    	int len = nums.length;
        int[][] dp = new int[len][2];
        dp[0][0] = 0;
        dp[0][1] = nums[0];
    
        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = dp[i - 1][0] + nums[i];
        }
        
        return Math.max(dp[len - 1][0], dp[len - 1][1]);
    }
}
           

時空複雜度 O ( n ) O(n) O(n)。