DP C# Solution, Beats 98%


  • 0
    H

    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];
    
    }
    

    }


  • 0
    V

    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]


  • 0
    H

    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.


Log in to reply
 

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