DP solution using static to accelerate from 324ms to 12ms in C++


  • 1
    class Solution {
    public:
        int numSquares(int n) {
            static vector<int> v{0, 1};
            int a = 0, b = 0, t = 0;
            while(v.size() <= n)
            {
                a = t= v.size();
                for(int i = sqrt(a); i > 0; --i)
                {
                    b = a-i*i;
                    t = min(t, !b? 1 : 1+v[b]);
                }
                v.push_back(t);
            }
            return v[n];
        }
    };

  • 1

    If you don't know Lagrange's four-square theorem, please check wiki first. In a summary, it's all about that the maximum will be 4 and in that case it will follow the following equation, otherwise it will be 1, 2, 3.

    4^k(8m+7)

    class Solution {
    public:
        int numSquares(int n) 
        {
            while(!(n&3)) n /= 4;
            if(n%8 == 7) return 4;
            for(int a = sqrt(n); a > 0; --a)
            {
                int b = sqrt(n-a*a);
                if(a*a+b*b == n) return !b? 1 : 2;
            }
            return 3;
        }
    };

  • 0

    Can u explain this please?


  • 1

    Using DP as a hack, because it can store the essential info for us that we do not need to re-calculate it. In this case, we store the minimal numSquare for each number we encountered and then due to static feature, it will be not necessary for us to re-calculate it next time when we invoke this function. As for the searching process (to looking for the minimal numSquare), I think it's quite straight-forward and simple, since we have to check the searched numbers a-i*i to determine the current minimum, that's exactly why we should use DP here, static here is a trick.


  • 0

    Awesome, thank you!


  • 0

    Sure thing, dude!


Log in to reply
 

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