Perfect squares

/*
any n can contain the squares of natural numbers eg. 1,4,9,16,25...sqrt(n)*sqrt(n)
so we have to select minimum numbers among the square of natural numbers.
This is similar to Coin denomination problem where value will go from 1 to n and
denominations are 1,4,9,16,suppose we put it in array ie. arr
so,We will be having a 2d dp table in which i=1 to n and j=0 to sizeof(arr)-1;
Logic:Either you select the jth currency or not.
case 1: i==jth denomination so we can achieve that amount in only one step and smaller than that is not possible.
case 2: i< jth denomination so we can't select the current denomination so this amount can be achieved by not selecting this denomination.
case 3: i>jth denomination
  if(j==0): means we have only one denomination ie. 1 so with 1,we need i of 1    to make it equal to i,there is no any other option.
  else : we are having more than one denomination so either select this denomination or don't select.keep one          point in mind,if we select the denomination,then check for i-denomination row but in same column
         because same denomination can be repeated also.
*/

class Solution {
public:
    int numSquares(int n) {
        vector <int> arr;
        int k=sqrt(n);
        for(int i=1;i<=k;i++){
            arr.push_back(i*i);
        }
        int dp[n+1][arr.size()];
        for(int j=0;j<arr.size();j++) dp[0][j]=0;
        for(int i=1;i<n+1;i++){
            for(int j=0;j<arr.size();j++){
                if(i==arr[j]) dp[i][j]=1;
                else if(i>arr[j]){
                    if(j==0) dp[i][j]=i;
                    else dp[i][j]=min(dp[i-arr[j]][j]+1,dp[i][j-1]);
                }
                else dp[i][j]=dp[i][j-1];
            }
        }
        return dp[n][arr.size()-1];
    }
};