Explanation of the DP solution


  • 18
    J

    The most common solution for this problem is using DP, BFS or Number theory. Here I will give a brief explanation of the DP solution. The solution is as following:

    public int NumSquares(int n) {
           int[] DP = new int[n + 1];
            for (int i = 1; i <= n; i++)
            {
                int min= int.MaxValue;
                for (int j = 1; j * j <= i; j++)
                {
                    min= Math.Min(min, DP[i - j * j] + 1);
                }
                DP[i] = min;
            }
            return DP[n];
    }
    

    First of all, we created the DP array as usual. This DP array stands for the least number of perfect square numbers for its index. For example DP[13]=2 stands for if you want to decompose 13 into some perfect square numbers, it will contains at least two terms which are 33 and 22.

    After the initialization of the DP array. We want to iterate through the array to fill all indices. During each iteration we're actually doing this: dp[i] = 1 + min (dp[i-j*j] for j*j<=i). The formula itself is a little bit hard to understand. Here's an example of how it works: (C#)

    Suppose we want to get DP[13] and we already have the previous indices filled.

    DP[13] = DP[13-1x1]+DP[1] = DP[12]+1 = 3;

    DP[13] = DP[13-2x2]+DP[2x2] = DP[9]+1 = 2;

    DP[13] = DP[13-3x3] + DP[3x3] = DP[4] + 1 = 2;

    We pick the smallest one which is 2 so DP[13] = 2. Hope it helps.


  • 0

    Why do you explicitly set DP[1] = 1; instead of just starting i at 1? And if you think explicitly setting unnecessary base cases is good, then why not also add DP[2] = 2; and start i at 3?

    Btw, your text got messed up because some * got interpreted as markup and are now missing.


  • 0
    S

    Actually the base case is necessary, and the actual base case should be DP[0] = 0 (which may be set by the compiler when you "new" the array). For the above code, whenever i = j * j, it will reach DP[i - j * j] = DP[0].


  • 0
    This post is deleted!

  • 0
    S

    Lol. Sorry I wasn't the one who posted this algo. I agree with you that the 1-case is not needed. For the “multiple", it must be something wrong with this editor. It won't show up by simply typing the ""*(star).


  • 0
    This post is deleted!

  • 0
    S

    Oh. I meant @jim11 was the one (NOT ME) posted this solution. I am NOT HIM. I just added my comment like you did. When you referred to "your comment" I assumed that you mistook me as him. PLAGIARISM?? what's going on?


  • 0

    Ah ****, I didn't realize you're a different person, sorry :-)
    I now hid my thus nonsensical comments in shame...


  • 1
    A

    Nice solution. In case recursive DP is easier to understand for anyone (Like it is for me) here's my solution:

    public class Solution {
        public int numSquares(int n) {
            int[] cache = new int[n + 1];
            return numSquares(n, cache);
        }
    
        public int numSquares(int n, int[] cache) {
            if (n <= 1) {
                return Math.max(0, n);
            }
            if (cache[n] == 0) {
                cache[n] = Integer.MAX_VALUE;
                for (int i = 1; i * i <= n; i++) {
                    cache[n] = Math.min(
                        cache[n],
                        numSquares(n - i * i, cache) + 1
                    );
                }
            }
            return cache[n];
        }
    }

  • 0
    J

    You're right, I shoulda start from 0.


  • 0
    H

    I don't know how to get it's time complexity, could you explain it?


  • 0

    Thank You! Thank you for your explination saved me from BFS solution!


  • 0
    Y

    I like this solution! it is easier to come across than the tricky maths solutions...


  • 0
    T

    dude, DP[12]=3....


Log in to reply
 

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