Algorithm Notes
  • Introduction
  • Search & Backtracking 搜索与回溯
    • Tree 与 BackTracking 的比较
    • Subsets, Combination 与 Permutation
    • Subsets & Combinations & Combination Sum
    • 枚举法
    • N 皇后 + 矩阵 Index Trick
    • Sudoku 数独 + 矩阵 Index Trick
    • Word Ladder I & II
    • Number of ways 类
    • DFS flood filling
    • Strobogrammatic 数生成
    • String 构造式 DFS + Backtracking
    • Word Pattern I & II
    • (G) Binary Watch
    • (FB) Phone Letter Combination
    • 常见搜索问题的迭代解法
  • String,字符串类
    • 多步翻转法
    • Substring 结构和遍历
    • Palindrome 问题
    • Palindrome Continued
    • String / LinkedList 大数运算
    • 序列化与压缩
    • 5/24 String 杂题
    • Knuth–Morris–Pratt 字符串匹配
    • Lempel–Ziv–Welch 字符串压缩算法
    • (G) Decode String
    • (G) UTF-8 Validation
  • Binary Tree,二叉树
    • 各种 Binary Tree 定义
    • LCA 类问题
    • 三序遍历,vertical order
    • Post order traversal 的应用
    • Min/Max/Balanced Depth
    • BST
    • 子树结构
    • Level Order traversal
    • Morris 遍历
    • 修改结构
    • 创建 / 序列化
    • 子树组合,BST query
    • 路径与路径和
    • NestedInteger 类
    • (FB) 从 Binary Tree Path 看如何递归转迭代
    • (FB) Binary Tree Path 比较路径大小
    • 比较好玩的 Binary Tree 概率题
  • Segment & Fenwick Tree,区间树
    • Segment Tree 基础操作
    • Segment Tree 的应用
    • Fenwick Tree (Binary Indexed Tree)
    • Range Sum Query 2D - Immutable
  • Union-Find,并查集
    • Union-Find,并查集基础
    • Union-Find, 并查集应用
  • Dynamic Programming, 动态规划
    • 6/20, 入门 House Robber
    • 7/12, Paint Fence / House
    • 6/24, 滚动数组
    • 6/24, 记忆化搜索
    • 6/24, 博弈类 DP
    • 博弈类DP, Flip Game
    • 6/25, 区间类DP
    • 6/27, subarray 划分类,股票
    • 7/2, 字符串类
    • Bomb Enemies
    • 8/2,背包问题
    • (G) Max Vacation
    • (11/4新增) AST 子树结构 DP
  • LinkedList,链表
    • 6/9, LinkedList,反转与删除
    • 6/11, LinkedList 杂题
    • (FB) 链表的递归与倒序打印
  • LinkedIn 面经,算法题
    • 6/17, LinkedIn 面经题
    • 6/28, LinkedIn 面经题
    • 7/6, LinkedIn 面经
    • Shortest Word Distance 类
    • DFA Parse Integer
  • Two Pointers,双指针
    • 3 Sum, 3 Sum Closest / Smaller, 4 Sum
    • 对撞型,灌水类
    • 对撞型,partition类
    • Wiggle Sort I & II
    • 双指针,窗口类
    • 双指针,窗口类
    • Heap,排序 matrix 中的 two pointers
  • Bit & Math,位运算与数学
    • Bit Manipulation,对于 '1' 位的操作
    • Math & Bit Manipulation, Power of X
    • 坐标系 & 数值计算类
    • Add Digits
    • 用 int 做字符串 signature
  • Interval 与 扫描线
    • Range Addition & LCS
    • 7/5, Interval 类,扫描线
  • Trie,字典树
    • 6/9, Trie, 字典树
  • 单调栈,LIS
    • 4/13 LIS
    • 栈, 单调栈
    • Largest Divisible Subset
  • Binary Search 类
    • Matrix Binary Search
    • Array Binary Search
    • Find Peak Element I & II
    • **Median of Two Sorted Arrays
  • Graph & Topological Sort,图 & 拓扑排序
    • 有向 / 无向 图的基本性质和操作
    • 拓扑排序, DFS 做法
    • 拓扑排序, BFS 做法
    • Course Schedule I & II
    • Alien Dictionary
    • Undirected Graph, BFS
    • Undirected Graph, DFS
    • 矩阵,BFS 最短距离探索
    • 欧拉回路,Hierholzer算法
    • AI, 迷宫生成
    • AI, 迷宫寻路算法
    • (G) Deep Copy 无向图成有向图
  • 括号与数学表达式的计算
  • Iterator 类
  • Majority Element,Moore's Voting
  • Matrix Inplace Operations
  • 常见数据结构设计
  • (G) Design / OOD 类算法题
  • 随机算法 & 数据结构
  • (FB) I/O Buffer
  • (FB) Simplify Path, H-Index I & II
  • (FB) Excel Sheet, Remove Duplicates
  • Integer 的构造,操作,序列化
  • Frequency 类问题
  • Missing Number 类,元素交换,数组环形跳转
  • 8/10, Google Tag
  • (FB) Rearrange String k Distance Apart
  • Abstract Algebra
    • Chap1 -- Why Abstract Algebra ?
    • Chap2 -- Operations
    • Chap3 -- The Definition of Groups
Powered by GitBook
On this page
  • House Robber
  • 由此我们发现了 DP 的第一个性质: overlap subproblems.
  • 因此我们满足了 DP 的正确性性质: optimal substructure.
  • 此题的另外考点在于空间的优化。因为每一个 size = n 的问题只和前面的 2 个子问题相关,我们显然不需要存储所有的状态,而可以用滚动数组优化空间占用。 滚动数组的简单用法就是“膜” (=。=),即对 dp[] 的 index 取 mod,
  • 除数等于需要保存的状态数。
  • 在数组 index % mod 的做法其实相当于做了一个 circular buffer, 使得固定长度的数组收尾相接,依序覆盖。
  • 题外话,cicular buffer 很适合用于实现 fixed-size queue,一个 java 实现看一看这个帖子
  • House Robber II
  • 这题考察环形数组中,subproblem 的拆分与覆盖。
  • 不过我们不需要考虑所有的可能切分,因为只有相邻元素之间会出现问题。我们的 subproblem 不能再以 size = n 开始 top-down了,因为无法保证正确性; 但是 size = n - 1 的所有 subproblems,一定是正确的。我们只需要考虑,如何拆分 size = n - 1 的 subproblems,并且如何用他们构造出全局最优解。
  • 只需要把环形数组拆分成两个头尾不同的 size = n - 1 的 subproblems 就可以了:
  • 【1, 7, 5, 9, 2】
  • 下面的 subproblem 覆盖了所有不抢最后一座房子的 subproblems;
  • 【(1, 7, 5, 9) 2】
  • 如下的 subproblem 覆盖了所有不抢第一座房子的 subproblems;
  • 【1,(7, 5, 9, 2)】
  • 如果最后的最优解第一座和最后一座房子都不抢,也一定会被包含在左右两个 subproblem 的范围内,因为其 size = n - 2;
  • 【1, (7, 5, 9), 2】
  • 由于我们不能同时抢第第一和最后一座房子,上面两个 overlap subproblem 一定覆盖了所有子问题的最优解,并且符合全局最优解的 optimal substructure,保证了算法的正确性。
  • 易错点: 后半段数组的 index offset,合理的处置是用完全一样的 for loop,只在实际取元素的时候做 nums[i + 1],不然计算后半段以 i = 3 开始时,覆盖的 dp[] 位置是错的。
  • House Robber III
  • 这题其实很像 POJ 2342 Anniversary party ,区别在于这里的树只有两叉,结构简单很多。
  • 回顾下这章一开始对动态规划的总结,可以很容易看出来,这题的左右子树 subproblem 是 disjoint.
  • 因此这道题只有 optimal substructure,而没有 overlap subproblems.
  • 这道题只有 DP 的一个性质: optimal substructure,即用 subproblem (subtree) 的最优解可以构造出全局最优解。optimal substructure性质在 Tree 类问题中非常常见,因此遇到一个问题的时候,要注意按照其性质属性仔细辨别正确解法。
  • 在 Tree 上做递归的时候返回顺序已然是 bottom-up,相对于每一个节点,并没有重复计算,也没有 overlap subproblems,因此这只是一个正常的递归搜索问题,而不需要依赖 DP 进行优化。
  • dfs 时间复杂度已经是 O(n) , n = # of nodes

Was this helpful?

  1. Dynamic Programming, 动态规划

6/20, 入门 House Robber

PreviousDynamic Programming, 动态规划Next7/12, Paint Fence / House

Last updated 4 years ago

Was this helpful?

题本身不难,Easy 难度。

先从 Top-Down 的角度来想,如果我们定义 maxProfit(n) 为长度为 n 的 array 中所能得到的最大利益的话,不难看出在计算 maxProfit(n) 的时候,它的值只和前两个 subproblem 相关,即 maxProfit(n - 1) 和 maxProfit(n - 2).

由此我们发现了 DP 的第一个性质: overlap subproblems.

同时如果 maxProfit(n - 1) 和 maxProfit(n - 2) 都是其对应子问题的最优解的话,我们可以只利用这两个子问题的 solution,加上对当前元素的判断,构造出 maxProfit(n) 的最优解。

因此我们满足了 DP 的正确性性质: optimal substructure.

此题的另外考点在于空间的优化。因为每一个 size = n 的问题只和前面的 2 个子问题相关,我们显然不需要存储所有的状态,而可以用滚动数组优化空间占用。 滚动数组的简单用法就是“膜” (=。=),即对 dp[] 的 index 取 mod,

除数等于需要保存的状态数。

在数组 index % mod 的做法其实相当于做了一个 , 使得固定长度的数组收尾相接,依序覆盖。

题外话,cicular buffer 很适合用于实现 fixed-size queue,一个 java 实现看一看

public class Solution {
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        if(nums.length == 2) return Math.max(nums[0], nums[1]);

        int[] dp = new int[2];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

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

        return dp[(nums.length - 1) % 2];

    }
}

这题考察环形数组中,subproblem 的拆分与覆盖。

数组变成环形之后,就需要考虑首尾相接的问题了~ 理论上说,对于长度为 n 的环形数组,我们现在有了 n 种不同的切分方式,去处理长度为 n 的线性数组。

不过我们不需要考虑所有的可能切分,因为只有相邻元素之间会出现问题。我们的 subproblem 不能再以 size = n 开始 top-down了,因为无法保证正确性; 但是 size = n - 1 的所有 subproblems,一定是正确的。我们只需要考虑,如何拆分 size = n - 1 的 subproblems,并且如何用他们构造出全局最优解。

只需要把环形数组拆分成两个头尾不同的 size = n - 1 的 subproblems 就可以了:

【1, 7, 5, 9, 2】

下面的 subproblem 覆盖了所有不抢最后一座房子的 subproblems;

【(1, 7, 5, 9) 2】

如下的 subproblem 覆盖了所有不抢第一座房子的 subproblems;

【1,(7, 5, 9, 2)】

如果最后的最优解第一座和最后一座房子都不抢,也一定会被包含在左右两个 subproblem 的范围内,因为其 size = n - 2;

【1, (7, 5, 9), 2】

由于我们不能同时抢第第一和最后一座房子,上面两个 overlap subproblem 一定覆盖了所有子问题的最优解,并且符合全局最优解的 optimal substructure,保证了算法的正确性。

易错点: 后半段数组的 index offset,合理的处置是用完全一样的 for loop,只在实际取元素的时候做 nums[i + 1],不然计算后半段以 i = 3 开始时,覆盖的 dp[] 位置是错的。

public class Solution {
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        if(nums.length == 2) return Math.max(nums[0], nums[1]);

        int leftMax = helper(nums, 0);
        int rightMax = helper(nums, 1);

        return Math.max(leftMax, rightMax);
    }

    private int helper(int[] nums, int start){
        int max = 0;
        int[] dp = new int[2];
        dp[0] = nums[start];
        dp[1] = Math.max(nums[start], nums[start + 1]);

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

        return dp[(nums.length - 2) % 2];
    }
}

回顾下这章一开始对动态规划的总结,可以很容易看出来,这题的左右子树 subproblem 是 disjoint.

因此这道题只有 optimal substructure,而没有 overlap subproblems.

先贴一段错误的代码,思路就是用 level order 遍历整棵树,存下 curSum ,然后用 House Robber 一样的思路去做 DP. 错误的原因在于,不应该直接舍弃掉一层,因为层与层之间并不是 fully connected,比如[2,1,3,null,4],最优解是相邻两层上不相连的两个 node.

public class Solution {
    public int rob(TreeNode root) {
        if(root == null) return 0;

        List<Integer> lvlSum = new ArrayList<Integer>();

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        if(root != null) queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            int curSum = 0;
            for(int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                curSum += node.val;
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            lvlSum.add(curSum);
        }

        if(lvlSum.size() == 1) return lvlSum.get(0);
        if(lvlSum.size() == 2) return Math.max(lvlSum.get(0), lvlSum.get(1));

        int[] dp = new int[2];
        dp[0] = lvlSum.get(0);
        dp[1] = Math.max(lvlSum.get(0), lvlSum.get(1));

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


        return dp[(lvlSum.size() - 1) % 2];

    }
}

这道题只有 DP 的一个性质: optimal substructure,即用 subproblem (subtree) 的最优解可以构造出全局最优解。optimal substructure性质在 Tree 类问题中非常常见,因此遇到一个问题的时候,要注意按照其性质属性仔细辨别正确解法。

在 Tree 上做递归的时候返回顺序已然是 bottom-up,相对于每一个节点,并没有重复计算,也没有 overlap subproblems,因此这只是一个正常的递归搜索问题,而不需要依赖 DP 进行优化。

dfs 时间复杂度已经是 O(n) , n = # of nodes

public class Solution {
    public int rob(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return root.val;


        int leftLvl = 0, rightLvl = 0;
        int subleftLvl = 0, subrightLvl = 0;

        if(root.left != null){
            leftLvl = rob(root.left);
            subleftLvl = rob(root.left.left) + rob(root.left.right);
        }
        if(root.right != null){
            rightLvl = rob(root.right);
            subrightLvl = rob(root.right.left) + rob(root.right.right);
        }

        return Math.max(subleftLvl + subrightLvl + root.val, leftLvl + rightLvl);
    }
}

这题其实很像 ,区别在于这里的树只有两叉,结构简单很多。

House Robber
circular buffer
这个帖子
House Robber II
House Robber III
POJ 2342 Anniversary party