狗家onsite面经

感谢分享。顺序的话是不是可以从最外层推向最内层，然后dp[j] 存<rob, notRob>最大值的pair。不过我好奇用dfs with memo的方法理论上不也是dp嘛，他是说必须要用bottom up的dp吗？
刚才又想了一下，好像会造成循环依赖。所以想问一下题目有没有什么像原题一样的限制条件呢，比如每一行只能抢劫一家之类的？

xiana406 发表于 2021-4-6 05:50
有其他轮次的题目信息吗？这道题感觉定义dp[j]表示矩形((0, 0), (i, j))(假设用左上角，右下角代表矩形)小 ...

不行吧，即使是一维的情况，某一段区间[a, b]的最大rob值f(a, b)也不等于f(a, x) + f(x + 1, b)，其中a < x < b。本题二维的情况，肯定不能按照面积的关系来加吧。

xiana406 发表于 2021-4-6 19:50
有其他轮次的题目信息吗？这道题感觉定义dp[j]表示矩形((0, 0), (i, j))(假设用左上角，右下角代表矩形)小 ...

应该没有减法吧？因为最大值不会把不同区域加起来。会不会下面的更好？
dp[j] = max(dp[i - 2][j] + v[i][i][j], dp[i][j - 2] + v[i][j][i], dp[i - 2[j - 2] + v[i][j], [i] dp[i - 1][j]， dp[i][j - 1]， dp[i-1][j-1])

求大神指点[/i][/i][/i][/i][/i]

xiana406 发表于 2021-4-6 19:50
有其他轮次的题目信息吗？这道题感觉定义dp[j]表示矩形((0, 0), (i, j))(假设用左上角，右下角代表矩形)小 ...

这样应该是有问题的。矩形按 (AB) +(AC) - A 算 （ABC) 需要 +/- 可逆才行。

我能想到最好的方法是：
每行 m 个元素有 2^m 个状态 (每个抢或不抢，2^m 里有很多本身就不 valid），然后按行做 house robber，dp[i][k] 表示 i 行，状态为 k （1/0 抢或不抢的二进制表示）的最大收益。时间复杂度可以由裸 dfs 的 O(2^(m + n)) 变成 O(max(m, n) * 2^(2 * min(m, n)))，如果提前算好哪些状态不 valid，用 map 表示状态和状态之间的转移，可以进一步优化 time complexity

还有种办法是

graphene 发表于 2021-4-7 01:25
这样应该是有问题的。矩形按 (AB) +(AC) - A 算 （ABC) 需要 +/- 可逆才行。

我能想到最好的方法是：
...

感觉状态压缩dp是正解

graphene 发表于 2021-4-7 01:25
这样应该是有问题的。矩形按 (AB) +(AC) - A 算 （ABC) 需要 +/- 可逆才行。

我能想到最好的方法是：
...

2^m的复杂度也很可观了。除非能从这里面快速挑出来合法的子集。

    public int findMax(int[][] arr){        int m = arr.length, n = arr[0].length;
        int[][] dp = new int[m][n];
        // dp[i][j] represents if visit the current arr[i][j], the max it can achieve
        // then we have dp[i][j] = Math.max(dp[i-2..i][j-2..j]), 4 numbers
        int globalMax = 0;
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                // if invalid set to 0
                int num1 = dp[i-2][j-1];
                int num2 = dp[i-2][j];
                int num3 = dp[i-1][j-2];
                int num4 = dp[i][j-2];
                int max1 = Math.max(num1, num2);
                int max2 = Math.max(num3, num4);
                int max = Math.max(max1, max2);
                max += arr[i][j];
                globalMax = Math.max(max, globalMax);
                dp[i][j] = max;
            }
        }
        return globalMax;
    }
dp[i][j]代表起点到当前位置的矩阵且访问当前点的最大值，后面的数值都取决于前面的最大值，再用一个globalmax记录。逻辑上是用的induction，应该是这样。
不用记录dp[i-2][j-2]是因为dp[i][j-2]和dp[i-2][j]都包含了这种情况，之前的这4个max包含了所有情况。

只想到 O(2^(min(m, n)) * max(m, n))的DP

Blazer 发表于 2021-4-7 02:32
public int findMax(int[][] arr){        int m = arr.length, n = arr[0].length;
        int[][]  ...

按照原题的解法，avoid(也就是跟i, j相邻的cell)的值也可能比using(你的代码里所包含的值)大，所以max还得比较那三个相邻的值，除此之外我感觉这应该就是解法了。

或者每个cell可以存两个值(avoid, using)，这样每次dp就只要看相邻的三个值。其实这题本身跟买股票的最后一个变形题的方法更像。

1. Design一个 auto spell-checking: 讨论下来, 面试官想给我一个Collection<String> dictionary 表示字典, 让我设计一个数据结构, 实现一个API :  List<String> findKClosest(String word, int k) : 返回字典里所有的距离 word 的 edit distance <= k 的单词, 单词按照edit distance排序, 如果edit distance相同, 按照alphabetical排序 可以Trie + DFS + DP + TreeSet 实现  2. LC 57 + LC 1272 推广: design 一个数据结构, 支持三个api: add(int start, int end), remove(int start, int end), isExist(int start, int end):  能往这个数据结构里add 线段, remove 线段, 可以query某个线段是不是被现在数据结构里include 比如: add(1, 3)  add (2, 5)  add(7, 9) add(15, 20) 这时候内部有这样的线段 [1, 5] [7, 9] [15, 20], isExist(2,3): true  isExist(4, 6) false. 如果remove(4, 8) 内部的线段 [1,3] [9, 9] [15, 20]  3. Serialize/Deserialize Binary Tree: 但是面试官说 TreeNode 的 field是String, 可以是任意String. 我本来想用"," 间隔, 但面试官说val就可以是逗号, 并且可以任意Unicode组成的String TreeNode {     String val;     TreeNode left, rightl }