讨论/《零起步学算法》 - 例题:打家劫舍/
《零起步学算法》 - 例题:打家劫舍
共 11 个回复

C++

状态方程比较清晰的

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        // dp[i][0]:表示第 i 房子不偷;dp[i][1]:表示第 i 房子偷
        vector<vector<int>> dp(n + 1, vector (2, 0));
        for (int i = 1; i <= n; ++i) {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]);  // 传递下去,因为是累加收益
            dp[i][1] = dp[i-1][0] + nums[i-1];  // 偷 i 那么 i-1 只能不偷
        }
        return max(dp[n][0], dp[n][1]);
    }
};

摇摇晃摇,到底偷还是不偷,这是一个问题。

2
class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[n - 1];
    }
}
1
int rob(vector<int>& nums) {
    int size = nums.size();
    if (size == 0) return 0;
    if (size == 1) return nums[0];
    if (size == 2) return max(nums[0], nums[1]);

    int dp[nums.size()];
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);

    for (int i = 2; i < nums.size(); i++) {
        dp[i] = max(dp[i - 1], (dp[i - 2] + nums[i]));
    }

    return dp[size - 1];
}
1
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(2));

        dp[0][0] = 0;
        dp[0][1] = nums[0];

        for(int i = 1; i < n; i ++){
            //不偷第i家
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
            //偷第i家
            dp[i][1] = dp[i - 1][0] + nums[i];
        }
        return max(dp[n - 1][0], dp[n - 1][1]);
    }
};
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(2, vector<int>(2));

        dp[0][0] = 0;
        dp[0][1] = nums[0];

        for(int i = 1; i < n; i ++){
            dp[i & 1][0] = max(dp[(i - 1) & 1][0], dp[(i - 1) & 1][1]);
            dp[i & 1][1] = dp[(i - 1) & 1][0] + nums[i];
        }
        return max(dp[(n - 1) & 1][0], dp[(n - 1) & 1][1]);
    }
};
1

反着偷也很容易理解

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0]*(n+2)
        for i in range(n-1, -1, -1):
            dp[i] = max(nums[i]+dp[i+2], dp[i+1])
        return dp[0]
1

空间 O(1)O(1)

class Solution {
public:
    int rob(vector<int>& nums) {
        int len = nums.size();
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return nums[0];
        }
        int norob = 0, rob = nums[0];
        for (int i = 1; i < len; ++i) {
            int temp = norob;
            norob = max(norob, rob);
            rob = temp + nums[i];
        }
        return max(norob, rob);
    }
};
/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if (1 >= nums.length) { return 0 == nums.length ? 0 : nums[0]; }
    let dp = new Array(nums.length).fill(0);
    dp[0] = nums[0]; dp[1] = Math.max(dp[0], nums[1]);
    for (let i = 2; i < nums.length; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    return dp[nums.length - 1];
};
class Solution {
public:
    int rob(vector<int>& nums) {
        int first=0,second=0;
        for(auto& num:nums){
            int tmp=max(second,first+num);
            first=second;
            second=tmp;
        }
        return second;
    }
};
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[][] dp = new int[n][2];
        dp[0][1] = nums[0];
        for (int i = 1; i < n ;i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + nums[i]);
        }
        return Math.max(dp[n - 1][0], dp[n - 1][1]);
    }
}

JS版本

var rob = function(nums) {
    let len =nums.length;
    let dp = new Array(len).fill(0);
    dp[0] = nums[0];
    dp[1] = Math.max(dp[0],nums[1]);
    for(let i = 2;i<=len;i++){
        dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
    }
    return dp[len-1];
};