Leet code question name perfect square

#1

what mistake in this code?

#2

hello @ankit_verma

pls check ur code link . it is not correct.
share correct code link

#4
#5

change ur dp size rest is correct.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+3,1000000); // size should be atleast 3 becuase u are accesing dp[2] irrespective of n
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            for(int j=1;j*j<=n;j++){
                if(i-j*j>=0)
                dp[i]=min(dp[i],dp[i-j*j]+1);
            }
        }
      return dp[n];  
    }
};

``
#6

why would not the size (n+1) ??

#7

if n=1 then ur dp size will be 2 .
and maximum index that u can access is 1.

but u are accessing dp[2] without looking for n , this will give runtime error

1 Like