DP solutions along with a math, using static can accelerate the DP to the best - 4ms in C same as the math


  • 1
    //AC - 144ms - DP method;
    int numSquares(int n)
    {
        int *mins = (int*)malloc(sizeof(int)*(n+1)); //store the minimal number of the PerfectSquare;
        for(int i = 1; i <= n; i++)
        {
            int min = INT_MAX;
            int square = 1;
            for(int r=1; square <= i; r++) //traverse the previous result to get the min;
            {
                int t = mins[i-square]+1;
                min = t < min? t : min;
                square = r*r;
            }
            mins[i] = min;
        }
        return mins[n];
    }
    

    Another DP solution but optimised further to avoid redundant operation by static feature in C.

      //using static feature to avoid redundant searching;
    int helper(int n)
    {
      static int mins[1000000] = {0};
      static int i = 1;
      for(; i <= n; i++)
      {
          int min = INT_MAX;
          int square = 1;
          if(mins[i]) continue;
          for(int r=1; square <= i; r++)
          {
              int t = mins[i-square]+1;
              min = t < min? t : min;
              square = r*r;
          }
          mins[i] = min;
      }
      return mins[n];
    }
    
    //AC - 4ms;
    int numSquares(int n)
    {
      return helper(n);
    }
      
    

    //AC - 4ms - mathematical method;
    int numSquares(int n)
    {
        //Based on Lagrange's Four Square theorem, there 
        //are only 4 possible results: 1, 2, 3, 4.
        //The result is 4 if and only if n can be written in the form of 4^k*(8*m + 7).
        while(n%4 == 0)  n >>= 2;
        if(n%8 == 7) return 4;
        for(int a=0; a*a <= n; ++a) //consider 1 and 2;
        {
            int b = sqrt(n-a*a);
            if(a*a + b*b == n)
                return 1+!!a; //if a==0, then return 1 otherwise return 2;
        }
        return 3;
    }

  • 0

    The static one... you're doing it wrong. Very wrong. (You actually don't avoid any redundant searching.)


  • 0

    @StefanPochmann I've checked this again and indeed, there should be something wrong about it. But what's that exactly? Have any idea? Thanks a lot!


  • 0

    You made it static so that you can reuse the data but then you don't. You compute everything from scratch all the time, overwriting the previously computed values with the exact same values.


  • 0

    @StefanPochmann Thank you so much, you're perfectly right! I've updated it and now its time reduced dramatically to 10ms. Thank you, man!


  • 0

    Yep, that's one way to do it, though there's an even better one.

    You don't need the mins[0] = 0; anymore, btw.


  • 0

    @StefanPochmann Yes, I've updated further. So many thanks. Awesome!


  • 0

    Not sure what you did, but what I meant was to make i static as well. No need to search for the next uncomputed index when you can simply remember it.


  • 1

    @StefanPochmann Yes, that's right. Sorry about update - some mistakes. Indeed, now it's reduced further to 4ms avoiding so many checkings! Great! Thanks you!


Log in to reply
 

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