经典问题 — 打家劫舍

打家劫舍基本都可以用动态规划来解决。

房屋偷盗 #

剑指 Offer II 089. 房屋偷盗

环形房屋偷盗 #

剑指 Offer II 090. 环形房屋偷盗

维护一个 helper,设定 number 的起始位置,自底向上计算两次,取最大值。

var rob = function(nums) {
    if (nums.length === 0) {
        return 0
    }
    if (nums.length === 1) {
        return nums[0]
    }

    let result1 = helper(nums, 0, nums.length - 2)
    let result2 = helper(nums, 1, nums.length - 1)
    return Math.max(result1, result2)
};

var helper = function(nums, start, end) {
    let left = nums[start]
    let right = 0

    if (start < end) {
        right = Math.max(nums[start], nums[start+1])
    }

    for (let i = start+2; i <= end; i++) {
        let temp = left
        left = right
        right = Math.max(temp + nums[i], right)
    }
    return Math.max(left, right)
}

打家劫舍 III #

337. 打家劫舍 III

还是动态规划,但是数组变成了二叉树。

粉刷房子 #

剑指 Offer II 091. 粉刷房子

分成三个公式,分别表示 r(i)、g(i)、b(i)。

然后还是滚动数组的思想,只构造一个三行两列的二维数组,保存 (i-1) 和当前 i 的最小花费,最后做一下比较。

var minCost = function(costs) {
    let n = costs.length
    if (n === 1) {
        return Math.min(costs[0][0], costs[0][1], costs[0][2])
    }
    let dp = [[],[],[]]
    for (let i = 0; i < 3; i++) {
        dp[i] = [costs[0][i], 0]
    }
    for (let i = 1; i < n; i++){
        for (let j = 0; j < 3; j++){
            dp[j][i%2] = Math.min(dp[(j+2)%3][(i-1)%2], dp[(j+1)%3][(i-1)%2]) + costs[i][j]
        }
    }
    let last = (n-1)%2
    return Math.min(dp[0][last], dp[1][last], dp[2][last])
};

参考 #

经典动态规划:打家劫舍系列问题

本文共 387 字,上次修改于 Jul 9, 2024
相关标签: Algorithms