Maximal Square leetcode dp

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Hi, I was solving this dp question (Maximal square from leetcode).

Let a be the input array.
The correct recurrence relation goes like:
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1

Correct code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
#ifdef NAYAK
#include "/mnt/D/dual/c/debug.h"
#else
#define DEBUG(x...);
#endif
#define SPEEDUP ios_base::sync_with_stdio(false);cin.tie(NULL);
#define MOD 1000000007
int a[1001][1001],dp[1001][1001];
int rec(int r,int c){
	if(a[r][c]==0)return 0;
	if(dp[r][c]!=-1)return dp[r][c];
	int ans=1;
	if(r>0 && c>0){
		int len=min(rec(r-1,c-1),min(rec(r-1,c),rec(r,c-1)));
		ans=max(ans,1+len);
	}
	return dp[r][c]=ans;
}
void CLEAN(){
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			scanf("%d",&a[i][j]);
			dp[i][j]=-1;
		}
	}
	int ans=INT_MIN;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++)ans=max(ans,rec(i,j));
	}
	printf("%lld\n",ans*1LL*ans );
}
 
int32_t main(){
	
	int T=1;
	scanf("%d",&T);
	while(T--){
		CLEAN();
	}
 
 
	#ifdef NAYAK
	cerr << "-- RUN: " << (float)clock() / CLOCKS_PER_SEC << " s --" << endl;
	#endif
 
	return 0;
}

But i was doing something like:
int val=min(dp[i - 1][j], dp[i][j - 1])
if(a[i-val][j-val]==1)dp[i][j] = val+ 1

This relation is incorrect but i was not able to find a testcase where it is failing.

My code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
#ifdef NAYAK
#include "/mnt/D/dual/c/debug.h"
#else
#define DEBUG(x...);
#endif
#define SPEEDUP ios_base::sync_with_stdio(false);cin.tie(NULL);
#define MOD 1000000007
int a[1001][1001],dp[1001][1001];
int rec(int r,int c){
	if(a[r][c]==0)return 0;
	if(dp[r][c]!=-1)return dp[r][c];
	int ans=1;
	if(r>0 && c>0){
		int len=min(rec(r,c-1),rec(r-1,c));
		if(a[r-len-1][c-len-1]==1)ans=max(ans,1+len);
	}
	return dp[r][c]=ans;
}
void CLEAN(){
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			scanf("%d",&a[i][j]);
			dp[i][j]=-1;
		}
	}
	int ans=INT_MIN;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++)ans=max(ans,rec(i,j));
	}
	printf("%lld\n",ans*1LL*ans );
}
 
int32_t main(){
	
	int T=1;
	scanf("%d",&T);
	while(T--){
		CLEAN();
	}
 
 
	#ifdef NAYAK
	cerr << "-- RUN: " << (float)clock() / CLOCKS_PER_SEC << " s --" << endl;
	#endif
 
	return 0;
}

Can anyone point out a testcase where it fails.

	Rev.	Lang.	By	When	Δ	Comment
	en1		shashwat_nayak	2022-09-03 19:35:42	2737	Initial revision (published)

Rev.

Lang.

When

Comment

en1

shashwat_nayak

2022-09-03 19:35:42

2737

Initial revision (published)

History