# DP C# Solution, Beats 98%

• public class Solution {

``````public int NumSquares(int n) {
int[] dp = new int[n+1];

for( int j = 0; j <= n; j++){
int tmp = (int)Math.Sqrt(j);
if(tmp*tmp == j){
dp[j] = 1;
continue;
}

int minRes = Int32.MaxValue;
for(int i = 1; i <= tmp; i++){
minRes = Math.Min(minRes, dp[j-i*i]+1);
}
dp[j] = minRes;
}

return dp[n];

}
``````

}

• Hey, can you explain the below line please?

``````        minRes = Math.Min(minRes, dp[j-i*i]+1);
``````

What is the logic behind the understanding that we need only +1 fo dp[j-i*i]

• Let me explain the algorithm implemented by using DP:

dp[k] is defined as the least number of perfect squares which adds up to k.

1. If the number j itself is a perfect square, such as j = tmp * tmp for some tmp <j, then dp[j]=1, means this number itself contains a perfect square. This constructs base for our DP.

2. Now look at the DP loop:
for(int i = 1; i <= tmp; i++){
minRes = Math.Min(minRes, dp[j-i*i]+1);
}
we consider any number k = j - i * i which k is less than j. we immediately know
j = k + i * i so dp[k]+1 is a candidate for the least number of perfect squares in j, i.e. dp[j], since j is a sum of k and a perfect square i * i. We loop through each possible i here and the minimum of all dp[k]+1 for k = j - i * i would be our dp[j], according to the definition.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.