@ninijia 在 Leetcode每日一题练习 ------ 1277. 统计全为 1 的正方形子矩阵 中发帖
从Leetcode 每日一题练习继续讨论:
1277. 统计全为 1 的正方形子矩阵
1277. Count Square Submatrices with All Ones
题解
本题对于理解动态规划很有启发意义,数正方形这个任务让我们自己来做,一般会很快的将整个图中的所有大片正方形全部找到,然后依次计算包含的小正方形个数并加和,再计数落单的1并加和。
但这种解法显然是不能落实成算法来实现的,因为我们在“找”图中的所有大片正方形时处理的其实是整个图的全部信息,对图中全部数据都是并行化分析的,是通过一种“形”的思想来寻找这些正方形的。因此我们要考虑,一般而言,对于这样的图,设计算法来解决问题时必然要通过遍历图中数据(无论是按行还是按列)来获取某些信息从而解决问题,但这样的过程存在一个问题,即它不是“并行化”的,而是顺序执行的,这可能有些难理解,我们无论如何遍历数组,终究要从某个起点...