leetcode-Maximal Square-DP 중점
2287 단어 LeetCode
DP에 대한 질문은 state equation이라고 쓰십시오. 여기서 state는 square length rather than the required area. 를 선택합니다.이것은 2D의 dp이기 때문에 dp[x][y]=?.
여기 dp[x][y]는 (x, y)를 오른쪽 하각점으로 하는 최대 square의 가장자리 길이를 나타낸다.
여기서 약간 다른 것은 일반적인 dp문제의 결과가 바로 dp상태수조의 마지막 값이라는 것이다.여기에서 구한 것은 사실 전체 dp상태 수조의 최대 값이다
해석 참조http://www.cnblogs.com/jcliBlogger/p/4548751.html http://bookshadow.com/weblog/2015/06/03/leetcode-maximal-square/
class Solution(object):
def maximalSquare(self, matrix):
""" :type matrix: List[List[str]] :rtype: int """
if matrix == []:
return 0
m, n = len(matrix), len(matrix[0])
dp = [[0] * n for x in range(m)]
ans = 0
for x in range(m):
for y in range(n):
if x == 0 or y == 0:
dp[x][y] = int(matrix[x][y])
else:
if int(matrix[x][y]):
dp[x][y] = min(dp[x - 1][y - 1], dp[x][y - 1], dp[x - 1][y]) + 1
ans = max(ans, dp[x][y])# dp
return ans * ans이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
