当前位置:网站首页>leetcode:221. 最大正方形【dp状态转移的精髓】
leetcode:221. 最大正方形【dp状态转移的精髓】
2022-07-05 12:40:00 【白速龙王的回眸】
分析
dp[i][j]表示以(i, j)为右下角的最大正方形边长
第一行和第一列特殊
其他的话需要考虑精髓式子:
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
简直人间精华
ac code
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
ans = 0
# dp[i][j]表示以(i, j)为右下角的最大全1正方形面积
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:
# 精髓
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
总结
dp套路
关于找到一个全是1的最大正方形
边栏推荐
- Taobao short videos are automatically released in batches without manual RPA open source
- Docker configures redis and redis clusters
- 10 minute fitness method reading notes (1/5)
- JSON parsing error special character processing (really speechless... Troubleshooting for a long time)
- SAP UI5 DynamicPage 控件介绍
- The relationship between the size change of characteristic graph and various parameters before and after DL convolution operation
- 深度长文探讨Join运算的简化和提速
- UNIX socket advanced learning diary -ipv4-ipv6 interoperability
- Pinduoduo flag insertion remarks API
- 《信息系统项目管理师》备考笔记---信息化知识
猜你喜欢
HiEngine:可媲美本地的云原生内存数据库引擎
Transactions from December 27 to 28, 2021
Preliminary exploration of basic knowledge of MySQL
SAP SEGW 事物码里的 ABAP 类型和 EDM 类型映射的一个具体例子
Didi open source Delta: AI developers can easily train natural language models
Comprehensive upgrade of Taobao short video photosynthetic platform
Distributed cache architecture - cache avalanche & penetration & hit rate
2021.12.16-2021.12.20 empty four hand transaction records
DNS的原理介绍
前几年外包干了四年,秋招感觉人生就这样了..
随机推荐
10 minute fitness method reading notes (5/5)
A deep long article on the simplification and acceleration of join operation
Notes for preparation of information system project manager --- information knowledge
Kotlin变量
Transactions from December 29, 2021 to January 4, 2022
Rasa Chat Robot Tutorial (translation) (1)
使用 jMeter 对 SAP Spartacus 进行并发性能测试
Distributed solution - completely solve website cross domain requests
Wechat enterprise payment to change access, open quickly
CVPR 2022 | single step 3D target recognizer based on sparse transformer
在家庭智能照明中应用的测距传感芯片4530A
Insmod prompt invalid module format
NFT: how to make money with unique assets?
Taobao short video, why the worse the effect
奔跑,开路
自然语言处理系列(一)入门概述
Taobao product details API | get baby SKU, main map, evaluation and other API interfaces
Shi Zhenzhen's 2021 summary and 2022 outlook | colorful eggs at the end of the article
GPON technical standard analysis I
Kotlin function