当前位置:网站首页>leetcode:221. Maximum square [essence of DP state transition]
leetcode:221. Maximum square [essence of DP state transition]
2022-07-05 13:01:00 【White speed Dragon King's review】
analysis
dp[i][j] Said to (i, j) Is the largest square side length in the lower right corner
The first row and the first column are special
Other words need to consider the essence formula :
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
It's the essence of the world
ac code
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
ans = 0
# dp[i][j] Said to (i, j) It is the largest collection in the lower right corner 1 Square area
m, n = len(matrix), len(matrix[0])
dp = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
if i == 0 or j == 0:
dp[i][j] = 1
else:
# quintessence
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
ans = max(ans, dp[i][j] * dp[i][j])
return ans
summary
dp tricks
About finding one that's all 1 The largest square of
边栏推荐
- Simply take stock reading notes (1/8)
- 2021-12-22 transaction record
- 《2022年中國銀行業RPA供應商實力矩陣分析》研究報告正式啟動
- SAP UI5 DynamicPage 控件介绍
- 我在滴滴做开源
- About the single step debugging of whether SAP ui5 floating footer is displayed or not and the benefits of using SAP ui5
- Transactions from January 6 to October 2022
- 2021-12-21 transaction record
- Oppo Xiaobu launched Obert, a large pre training model, and promoted to the top of kgclue
- ABAP editor in SAP segw transaction code
猜你喜欢
Overflow toolbar control in SAP ui5 view
SAP SEGW 事物码里的 Association 建模方式
Tips and tricks of image segmentation summarized from 39 Kabul competitions
A specific example of ABAP type and EDM type mapping in SAP segw transaction code
RHCSA5
It's too convenient. You can complete the code release and approval by nailing it!
Introduction to sap ui5 flexiblecolumnlayout control
初次使用腾讯云,解决只能使用webshell连接,不能使用ssh连接。
石臻臻的2021总结和2022展望 | 文末彩蛋
实战模拟│JWT 登录认证
随机推荐
SAP self-development records user login logs and other information
Introduction to sap ui5 dynamicpage control
DNS的原理介绍
Simply take stock reading notes (2/8)
将函数放在模块中
Taobao short video, why the worse the effect
阿里云SLB负载均衡产品基本概念与购买流程
Concurrent performance test of SAP Spartacus with JMeter
超高效!Swagger-Yapi的秘密
##无监控,不运维,以下是监控里常用的脚本监控
2021-12-22 transaction record
PyCharm安装第三方库图解
自然语言处理系列(一)入门概述
A specific example of ABAP type and EDM type mapping in SAP segw transaction code
实战模拟│JWT 登录认证
Why is your next computer a computer? Explore different remote operations
【云原生】Nacos中的事件发布与订阅--观察者模式
uni-app开发语音识别app,讲究的就是简单快速。
解决uni-app配置页面、tabBar无效问题
RHCSA1