关于动态规划:DP-就是暴力暴力就是艺术

4次阅读

共计 3233 个字符，预计需要花费 9 分钟才能阅读完成。

https://leetcode-cn.com/probl…

给定一个方阵，其中每个单元 (像素) 非黑即白。设计一个算法，找出 4 条边皆为彩色像素的最大子方阵。返回一个数组 [r, c, size]，其中 r, c 别离代表子方阵左上角的行号和列号，size 是子方阵的边长。若有多个满足条件的子方阵，返回 r 最小的，若 r 雷同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。示例 1:

输出:
[[1,0,1],
   [0,0,1],
   [0,0,1]
]
输入: [1,0,2]
解释: 输出中 0 代表彩色，1 代表红色，标粗的元素即为满足条件的最大子方阵
示例 2:

输出:
[[0,1,1],
   [1,0,1],
   [1,1,0]
]
输入: [0,0,1]
提醒：matrix.length == matrix[0].length <= 200

动静布局

暂无

看了下数据范畴，矩阵大小不超过 $200 \times 200$，因而答案应该就是暴力，这个数据范畴差不多 N 的三次方的复杂度都能够通过，其中 N 为矩阵的边长。起因我也在之前的文章来和大家聊聊我是如何刷题的（第三弹）中讲过了，那就是 $200^3$ 刚好是是 800 万，再多就很容易超过 1000 万 了。

乍一看，这道题和 221. 最大正方形，实则不然。这道题是能够空心的，只有边长是局部都是 0 即可，这就齐全不同了。

如下图，红色局部就是答案。只须要保障边全副是 0 就好了，所以外面有一个 1 无所谓的。

咱们无妨从部分动手，看能不能关上思路。

这是一种罕用的技巧，当你面对难题无从下手的时候能够画个图，从非凡状况和部分状况开始，帮忙咱们关上思路。

比方我想计算以如下图红色格子为右下角的最大黑方阵。咱们能够从以后点向上向左扩大直到非 0。

在下面的例子中，不难看出其最大黑方阵不会超过 min(4, 5)。

那答案间接就是 4 么？对于这种状况是的，然而也存在其余状况。比方：

因而解空间上界尽管是 4，然而下界依然可能为 1。

下界为 1 是因为咱们只对值为 0 的格子感兴趣，如果格子为 0，最差最大方阵就是本身。

下面我曾经将算法锁定为暴力求解了。对于解空间的暴力求解怎么做？无非就是 枚举所有解空间，最多减减枝。

直白一点来说就是：

1 能够么？
2 能够么？
3 能够么？
4 能够么？

这叫做非凡。

如果你曾经搞懂了这个非凡状况，那么个别状况也就不难了。

算法形容：

从左到右从上到下扫描一次矩阵。
如果格子值是 0，则别离向上和向左扫描直到第一个不是 0 的格子，那么最大方阵的上界就是 min(向左延长的长度, 向上延长的长度)。
逐渐尝试[1, 上界] 直到无奈造成方阵，最初可行的方阵就是以以后点能造成的最大方阵。
扫描过程保护最大值，最初返回最大值以及顶点信息即可。

当初的难点只剩下第三点局部 如何逐渐尝试[1, 上界]。实际上这个也不难，只须要：

在向左延长的同时向上探测
在向上延长的同时向左探测

看一下图或者好了解一点。

如上图就是尝试 2 是否可行，如果可行，咱们持续 贪得无厌，直到不可行或者到上界。

接下来，剖析一下算法的工夫复杂度。

因为每一个为 0 的点都须要向左向上探测，那么最坏就是 O(N)，其中 N 为边长。
向左向上的同时须要持续探测，这个复杂度最坏的状况也是 O(N)。

因为咱们须要对最多 $O(N^2)$ 个点执行下面的逻辑，因而总的工夫复杂度就是 $$O(N^4)$$

而实际上每一个格子都是一个独立的子问题，因而能够应用一个 memo（比方哈希表）将每个格子的扩大后果保存起来，这样能够将复杂度优化到 $O(N^3)$。

比方下面提到的向上向左探测的过程，如果下面和右面格子的扩大后果曾经计算出来了，那么间接用就行了，这部分延长的复杂度能够升高到 $O(1)$。因而不难看出，以后格子的计算依赖于左侧和上方格子，因而应用 从左到右从上到下扫描矩阵 是正确的抉择，因为咱们须要在遍历当以后格子的时候 左侧和上方格子的后果曾经被计算出来了。

(4,5) 找到上方相邻的格子，如果是 1 间接返回。
如果上方格子值是 0，去 memo 中查问。
memo 返回后果，咱们只须要将这个后果 + 1 就是能够向上延长的最大长度了。

比方当初要计算以坐标(4,5) 为右下角的最大方阵的边长。第一步要向上探测到 (3,5)，达到(3,5) 之后无需持续往上延长而是从 memo 中获取。(4,5) 上方的 0 的格子就是(3,5) 上方的格子个数 + 1。

最初一个问题。什么数据结构能够实现下面查问过程 $O(1)$ 工夫呢？hashmap 能够，数组也能够。

应用哈希 map 的益处是无非当时开拓空间。毛病是如果数据量太大，可能会因为哈希表的抵触解决导致超时。比方石子游戏应用哈希表存就很容易超时。
应用数组益处和害处简直和哈希表是相同的。数组须要实现指定大小，然而数组是不会抵触的，也不须要计算哈希键，因而在很多状况下性能更好。进一步应用数组这种内存间断的数据结构对 CPU 敌对，因而同样复杂度会更快。而哈希表应用了链表或者树，因而对 CPU 缓存就没那么敌对了。

综上，我举荐大家应用数组来存储。

这道题差不多就是这样了。实际上，这就是动静布局优化，其实也没什么神奇嘛，很多时候都是 暴力枚举 + 记忆化 而已。

代码反对：Java，Python

Java Code:

class Solution {public int[] findSquare(int[][] matrix) {int [] res = new int [0];
        int [][][] dp = new int [2][matrix.length+1][matrix[0].length+1];
        int max = 0
        for(int i=1;i<=matrix.length;i++){for(int j=1;j<=matrix[0].length;j++){if(matrix[i-1][j-1]==0){dp[0][i][j] = dp[0][i-1][j]+1;
                    dp[1][i][j] = dp[1][i][j-1]+1;
                    int bound = Math.min(dp[0][i][j], dp[1][i][j]);
                    for(int k=0;k<bound;k++){if(dp[1][i-k][j]>=k+1&&dp[0][i][j-k]>=k+1){if(k+1>max){res = new int [3];
                                max = k+1;
                                res[0] = i-k-1;
                                res[1] = j-k-1;
                                res[2] = max;
                            }
                        }
                    }
                }
            }
        }
        return res;
    }
}

Python Code:

class Solution:
    def findSquare(self, matrix: List[List[int]]) -> List[int]:
        n = len(matrix)
        dp = [[[0, 0] for _ in range(n + 1)] for _ in range(n + 1)]
        ans = []
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if matrix[i - 1][j - 1] == 0:
                    dp[i][j][0] = dp[i-1][j][0] + 1
                    dp[i][j][1] = dp[i][j-1][1] + 1
                    upper = min(dp[i][j][0], dp[i][j][1])
                    for k in range(upper):
                        if min(dp[i-k][j][1], dp[i][j-k][0]) >= k + 1:
                            if not ans or k + 1 > ans[2]:
                                ans = [i-k-1, j-k-1, k + 1]

        return ans

复杂度剖析