切换主题
打家劫舍篇
打家劫舍
- 状态定义：
dp[i] = x，表示前i个房子能偷盗的最高金额为x； base case：dp[0] = nums[0], dp[1] = Math.max(nums[0], nums[1])；- 状态转移方程：
dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1])。
JavaScript
const rob = nums => {
const len = nums.length
if (len === 1) return nums[0]
let dp0 = nums[0], dp1 = Math.max(nums[0], nums[1])
for (let i = 2; i < len; i++) {
[dp0, dp1] = [dp1, Math.max(dp1, dp0 + nums[i])]
}
return dp1
}时间复杂度：O(n)；空间复杂度：O(1)。
打家劫舍 II
由于成环，故首位的房屋只能偷盗一个。
JavaScript
const rob = nums => {
const len = nums.length
if (len === 1) return nums[0]
const R = copy => {
const len = copy.length
if (len === 1) return copy[0]
let dp0 = copy[0], dp1 = Math.max(copy[0], copy[1])
for (let i = 2; i < len; i++) {
[dp0, dp1] = [dp1, Math.max(dp1, dp0 + copy[i])]
}
return dp1
}
const m1 = R(nums.slice(0, len - 1))
const m2 = R(nums.slice(1))
return Math.max(m1, m2)
}时间复杂度：O(n)；空间复杂度：O(1)。
打家劫舍 III
- 状态定义：
dp = [0, 0]，dp[0], dp[1]分别表示当前节点不偷、偷时的最高金额； base case：dp = [0, 0]；- 状态转移方程：
dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); dp[1] = left[0] + right[0] + root.val。
JavaScript
const rob = root => {
// 后续遍历
const dfs = node => {
const dp = [0, 0]
if (!node) return dp
const [l, r] = [dfs(node.left), dfs(node.right)]
// 当前节点不偷时，取 左孩子能偷到的最高金额 + 右孩子能偷到的最高金额
dp[0] = Math.max(l[0], l[1]) + Math.max(r[0], r[1])
// 当前节点偷，取 当前节点值 + 左孩子自己不偷时能得到的最高金额 + 右孩子自己不偷时能得到的最高金额
dp[1] = node.val + l[0] + r[0]
return dp
}
const dp = dfs(root)
return Math.max(dp[0], dp[1])
}时间复杂度：O(n)；空间复杂度：O(n)。