经典算法题之Maximal Square

作者:叶 虎

编辑:邓高锦

Maximal Square是道非常有意思的算法题。它是一个典型的动态规划问题,同时也是2017京东面试题,2016华为机考题。

1

题目描述:

有一个n*m大小的矩阵,其元素值为0或者1,求这个矩阵中全有1组成的最大方块其大小。

2

输入描述

每个输入包含一个测试用例。每个测试用例的第一行包含两个整数n(2<= n <= 50),m(2<= n <= 50),分别表示矩阵matrix的行数与列数。接下来的每一行是该矩阵的每一行元素,其取值为1或者0。

3

输出描述

输出矩阵中全有1组成的最大方块其大小。

4

输入例子

4 6

1 1 0 1 1 1

0 1 1 1 1 1

1 1 0 1 1 1

1 1 0 0 1 1

5

输出例子

3

思路分析:

本题为一个典型的动态规划问题,因此可以使用动态规划的思想进行。动态规划重要的一个特点是要复用子问题。

假设以matrix[i][j]为右下顶点的最大方块的大小为dp[i][j]。那么dp[i][j]的计算否可以复用比其更小的子问题呢?不难想象,如果matrix[i][j]=0,那么dp[i][j]=0。当matrix[i][j]=1时,此时要考察dp[i-1][j-1],dp[i-1][j]及dp[i][j-1],这是由于以matrix[i][j]的为右下顶点的最大方块由上面三个位置决定,而且是木桶效应,由最小值所决定,即dp[i][j]=min{dp[i-1][j-1], dp[i-1][j], dp[i][j-1]} + 1。考虑到边界条件,可以得到最终的递归方程为:

只需要找到最大的dp[i][j]值即得到最大方块的大小。整个算法的时间复杂度与空间复杂度均为O(n*m)。

具体实现代码(C++)

本文只是Maximal Square算法题其中的一种解法,在此抛砖引玉。

原文发布于微信公众号 - 机器学习算法全栈工程师(Jeemy110)

原文发表时间:2017-09-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mathor

从暴力递归到动态规划

 动态规划没有那么难,但是很多老师在讲课的过程中讲的并不好,由此写下一篇文章记录学习过程

2011
来自专栏数值分析与有限元编程

有限元 | 二次样条梁单元

样条梁单元是样条函数与有限元法相结合的产物。有限元法将结构分割成若干单元,位移场采用分段插值或者分区插值。常用的插值方法有Lagrange插值,Hermite插...

3838
来自专栏算法channel

机器学习储备(10):numpy之RandomState() 和 axis

1 RandomState RandomState是一个伪随机数发生器,这是一个numpy的类,其中包括的方法有:rand,randint,uniform 等。...

3456
来自专栏Java Web

最长公共子序列问题

问题描述: 求两个字符序列的公共最长子序列。 ---- 最长公共子串 在回到子序列问题之前,先来了解一下子串的问题。 例如,HISH和FISH两个字符序列的公...

3514
来自专栏章鱼的慢慢技术路

《算法图解》第八章_贪婪算法_集合覆盖问题

4476
来自专栏Python小屋

详解Python科学计算扩展库numpy中的矩阵运算(1)

首先解答上一篇文章中使用with关键字让你的Python代码更加Pythonic最后的习题,该题答案是False,原因在于内置函数sorted()的参数reve...

2874
来自专栏数说工作室

SAS里的平行世界 | 【SAS Says · 扩展篇】IML:1.入门

本节目录: 1. IML基本语句 2. 标量、向量与矩阵 (1)定义标量 (2)定义向量 (3)定义矩阵 3. 矩阵的元素运算 (1...

3956
来自专栏专知

【干货】计算机视觉实战系列03——用Python做图像处理

【导读】专知成员Hui上一次为大家介绍Matplotlib的使用,包括绘图,绘制点和线,以及图像的轮廓和直方图,这一次为大家详细讲解Numpy工具包中的各种工具...

44810
来自专栏小樱的经验随笔

容斥原理

容斥原理 对容斥原理的描述 容斥原理是一种重要的组合数学方法,可以让你求解任意大小的集合,或者计算复合事件的概率。 描述 容斥原理可以描述如下: 要计算几个...

4197
来自专栏钱塘大数据

R语言的常用函数速查

一、基本 1.数据管理 vector:向量 numeric:数值型向量 logical:逻辑型向量character;字符型向量 list:列表 data....

3089

扫码关注云+社区