동적 기획 학습 - Leetcode - 1277 문제 - 통 계 는 모두 1 의 정사각형 자 사각형 개수
예시 1:
입력: matrix = [0, 1, 1], [1, 1, 1], [0, 1, 1, 1] 출력: 15 해석: 변 길이 가 1 인 정사각형 은 10 개 입 니 다.변 길이 가 2 인 정사각형 은 4 개다.변 길이 가 3 인 정사각형 은 하나 다.정사각형 의 총수 = 10 + 4 + 1 = 15.
출처: 스냅 백 (LeetCode) 링크:https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones 저작권 은 인터넷 에 귀속 된다.상업 전 재 는 공식 권한 수여 에 연락 하 십시오. 비 상업 전 재 는 출처 를 밝 혀 주 십시오. * *
문제 풀이 사고 dp [i] [j] 는 자신 을 정사각형 으로 저장 한 다음 에 주위 의 세 개의 dp [i - 1] [j] dp [i] [j - 1] dp [i - 1] [j - 1] 의 개 수 를 보고 가장 작은 개 수 를 취한 다. 왜냐하면 하나의 정사각형 을 구성 하려 면 0 이 있 는 지, 최소 0 이 아 닌 지 를 봐 야 하기 때문에 2 단계 정사각형 을 구성 해 야 한다.유추 가 최소 1 이 아니라면 3 단 계 를 구성 할 수 있다.
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int row=matrix.size();//
int col=matrix[0].size();//
int ans=0;
vector<vector<int>>dp(row+1,vector<int>(col+1,0));
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
if(i==0||j==0)dp[i][j]=matrix[i][j];//
if(matrix[i][j]==1)
{
dp[i+1][j+1]=min(min(dp[i+1][j],dp[i][j+1]),dp[i][j])+1;
// dp +1 （ ）；
ans+=dp[i+1][j+1];
}
}
}
return ans;
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
124. 두 갈래 나무의 최대 경로와 leetcode비공 두 갈래 트리를 지정하고 최대 경로와 를 되돌려줍니다. 본고에서 경로는 나무의 임의의 노드에서 출발하여 임의의 노드에 도달하는 서열로 정의되었다.이 경로는 루트 노드를 거치지 않고 하나 이상의 노드를 포함합니다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
