经典算法题之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 条评论
登录 后参与评论

相关文章

来自专栏进击的程序猿

seq2seq模型之raw_rnn

本文是seq2seq模型的第二篇,主要是通过raw_rnn来实现seq2seq模型。 github地址是:https://github.com/zhuanxu...

1332
来自专栏专注研发

(floyd)佛洛伊德算法

Floyd–Warshall(简称Floyd算法)是一种著名的解决任意两点间的最短路径(All Paris Shortest Paths,APSP)的算法。从表...

1573
来自专栏来自地球男人的部落格

TensorFlow中CNN的两种padding方式“SAME”和“VALID”

在用tensorflow写CNN的时候,调用卷积核api的时候,会有填padding方式的参数,找到源码中的函数定义如下(max pooling也是一样): ...

5665
来自专栏Python小屋

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

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

2634
来自专栏null的专栏

挑战数据结构和算法——跳台阶问题

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? image.png 方法: int get_kind(int n...

2676
来自专栏King_3的技术专栏

leetcode-48-旋转图像

你必须在原地旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

803
来自专栏深度学习之tensorflow实战篇

Python基础整理操作积累

Python编程积累 列表内容 Python基础 for变化量的灵活应用 for x,y in [[0,1],[0,2],[1,2]]: d...

32810
来自专栏炉边夜话

考场安排---图的着色原理之运用

试设计一算法,当给定一个图时G=(V,E),|V|=n,(Vi,Vj)ЄE,当且仅当有一个同学选了课程i和课程j,试给出一个考试安排方案N1,N2,N3…Nk,...

731
来自专栏tkokof 的技术,小趣及杂念

一种稀疏矩阵的实现方法

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/tkokof1/article/details/828...

371
来自专栏PPV课数据科学社区

【学习】ggplot2绘图入门系列之二:图层控制与直方图

如前文所述,ggplot2使用图层将各种图形元素逐步添加组合,从而形成最终结果。第一层必须是原始数据层,其中data参数控制数据来源,注意数据形式...

2586

扫码关注云+社区