🦁
Voyz的算法笔记
  • Voyz的算法笔记
  • 归纳总结
    • 排序算法
    • 二分法
    • 滑动窗口
    • 双指针
    • 动态规划
    • DFS/回溯算法
    • BFS
    • 贪心算法
  • 排序算法
    • 冒泡排序
    • 选择排序
    • 插入排序
    • 希尔排序
    • 归并排序
    • 快速排序
    • 堆排序
    • 计数排序
    • 桶排序
    • 基数排序
  • 数组
    • 数组中第k大的元素
    • 最长上升子数组
    • 构建乘积数组
    • 和为 s 的连续正数序列
    • 和为 s 的两个数字
    • 连续子数组的最大和
    • 排序数组中的出现次数
    • 奇数位于偶数前
    • 数组中超过一半的数字
    • 旋转数组的最小数字
    • 左旋转字符串
    • 合并有序数组
  • 字符串
    • 电话号码的字母组合
    • 判断回文字符串
    • 生成有效括号
    • 找出回文子串
    • 最长公共前缀
    • 翻转单词顺序
    • 替换空格
    • Z字形变换
  • 矩阵
    • 矩阵置零
    • 螺旋矩阵
    • 搜索二维矩阵
    • 旋转图像
    • 杨辉三角
    • 矩阵查找
    • 矩阵中的路径
    • 顺时针打印矩阵
  • 栈和队列
    • 定义栈数据结构
    • 根据身高重建队列
    • 计算后缀表达式
    • 中缀转后缀
    • 包含 min 函数的栈
    • 从尾到头打印链表
    • 队列的最大值
    • 滑动窗口的最大值
    • 用两个栈实现队列
    • 栈的压入、弹出序列
    • 判断括号有效
  • 哈希表
    • 第一个只出现一次的字符
    • 数组中重复的数字
    • LRU 缓存机制
  • 链表
    • 反转链表
    • 反转链表部分链表
    • 复制带随机指针的链表
    • 复制复杂链表
    • 删除倒数第n个节点
    • 合并两个排序的链表
    • 链表倒数第 k 个节点
    • 两个链表的第一个公共节点
    • 删除链表的节点
    • 环形链表入环位置
    • 链表是否有环
    • 判断回文链表
    • K 个一组翻转链表
  • DFS/回溯算法
    • 不重复字母构成字符串
    • 单词搜索
    • 岛屿数量
    • 分割回文串
    • 全排列
    • 数组组合总和
    • 子集
    • 机器人的运动范围
  • BFS
    • 从上到下打印二叉树
    • 从上到下打印二叉树II
    • 从上到下打印二叉树III
    • 二叉树的最小深度
    • 打开转盘锁
  • 动态规划
    • 打家劫舍I
    • 打家劫舍 II
    • 打家劫舍 III
    • 股票问题汇总
    • 零钱兑换
    • 爬楼梯
    • 最大正方形
    • 把数字翻译成字符串
    • 丑数
    • 斐波那契数列
    • 礼物的最大价值
    • 圆圈中最后剩下的数字
    • 添加符号得到目标和方法数
  • 树
    • 【二叉树】翻转
    • 【二叉树】构造by前序中序
    • 【二叉树】构造by中序后序
    • 【二叉树】合并
    • 【二叉树】镜像
    • 【二叉树】判断对称
    • 【二叉树】前中后序遍历
    • 【二叉树】深度
    • 【二叉树】展开为链表
    • 【二叉树】直径
    • 【二叉树】重复的子树
    • 【二叉树】最近公共祖先
    • 【二叉树】B是A的子结构
    • 【二叉搜索树】第K大元素
    • 【二叉搜索树】第K小元素
    • 【二叉搜索树】构造/遍历
    • 【二叉搜索树】判断
    • 【二叉搜索树】判断后序遍历
    • 【二叉搜索树】转累加树
    • 【二叉搜索树】转排序双向链表
    • 【二叉搜索树】最近公共祖先
    • 【红黑树】构造
    • 【路径和】根到叶子节点
    • 【路径和】为某一值的集合
    • 【路径和】最大值
    • 【平衡二叉树】判断
    • 【对称二叉树】判断
    • 【完美二叉树】填充右侧指针
    • 【依赖关系树】打包顺序数组
    • 【最大二叉树】构建
  • 位运算
    • 比特位计数
    • 出现超过一半的数字
    • 汉明距离
    • Pow(x, n)
    • 不用加减乘除做加法
    • 二进制中 1 的个数
    • 两个只出现一次的数字
  • 贪心算法
    • 加油站
    • 剪绳子
    • 跳跃游戏
    • 无重叠区间
    • 用最少数量的箭引爆气球
  • 双指针
    • 接雨水
    • 盛最多水的容器
    • 长度最小的连续子数组
    • n数之和
  • 分治算法
    • 为运算表达式设计优先级
  • 二分法
    • 缺失的数字
    • 旋转数组的最小元素
    • 排序数组中查找左右区间
由 GitBook 提供支持
在本页
  • LeetCode 337. 打家劫舍 III
  • 题目
  • 题解

这有帮助吗?

  1. 动态规划

打家劫舍 III

上一页打家劫舍 II下一页股票问题汇总

最后更新于3年前

这有帮助吗?

题目

在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。

计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:

输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

题解

DP

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
const dp_table = new Map()
var rob = function(root) {
    // dp[root] = max(root.val+rob(四个孙子结点),rob(两个子节点))

    if(root == null) return 0;
    if(dp_table.has(root)) return dp_table.get(root);

    const do_rob = root.val + 
    (!!root.left ? rob(root.left.left)+rob(root.left.right) : 0) + 
    (!!root.right ? rob(root.right.left)+rob(root.right.right) : 0);
    const not_rob = rob(root.left) + rob(root.right);

    const res = Math.max(do_rob,not_rob)
    dp_table.set(root,res);

    return res;
};
LeetCode 337. 打家劫舍 III