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
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
Can anyone point out a testcase where it fails.
Stress testing
Thank You, will try stress testing from next time.