I have a new trick to speed up DP: Java beat 95%, but Python still TLE...


  • 2
    X
    public int numSquares(int n) {
        int[] record = new int[n+1];
        for(int i=1;i<=n;++i){
            record[i] = i;
            for(long j=(int)Math.sqrt(i);j*j*(record[i]-1)>=i;--j){
                record[i] = Math.min(record[(int)(i-j*j)]+1,record[i]);
            }
        }
        return record[n];
    }
    

    I'm modifying on the most voted answer.

    For the loop, I do from sqrt(i) to 1 instead of 1 to sqrt(i), the idea is to find good answer faster, and then use j×j×(record[i]-1)>=i to end the loop.

    Firstly, you should view j as your biggest number in your answer (that's why I'm doing from sqrt(i) to 1). Then, the idea is that, if it is impossible to beat your current best result, you should quit. Why it would be impossible? Because you have an upper bound on the amount of number you can use (your current best result), and you have an upper bound on the number you can use (j), you multiple this two, at some point, it is impossible to sum up to your target. When this happens, you should quit.

    E.g., we are doing 12, if we already find an answer with 3 numbers, then we don't need to do j<=2, because for j=2, that's your biggest number (2×2=4), obviously you cannot beat current best answer (3 numbers), because to beat that, you can only use 2 numbers, and the maximum number you can use is only 4 (so the sum would be only 2×4=8, less than 12). Using j=1 will give even worse answer.

    However, my Python uses even better optimization still TLE, haha.


  • 0
    R

    Good job.
    I'm still confused with the loop ending condition. Could you explain more? Why should smaller j would get worse result?


  • 0
    X

    I don't think I was being clear enough.

    I edited my post. There are two keys:

    1. you should view j as your biggest number in your answer (that's why I loop from sqrt(i) to 1);
    2. when you are only using your biggest number to build the answer (no other smaller numbers), you still cannot beat your current best answer, you should quit.

  • 0
    R

    I got it! this is a great example of how to refine the algorithm. Thanks for your explanation bro, I'm so impressed :)

    Just a little error: for 12, we don't need to do j < 2. We got the record 3 when j == 2.


  • 0
    A

    The solution is wrong, for n = 84732 it returns back 84732 instead of 4.


  • 0
    X

    Thanks. My solution is AC but obviously your testcase is bigger :)

    I looked into the code, the reason is your testcase makes jj(record[i]-1) bigger than int, then it becomes negative unexpectedly.

    There are other better fixes, but the simplest fix is to make j long instead of int :)


  • 0
    C

    bad case: 143523. output is 143523

    record[i] = i; should change to

    record[i] = Math.min(i, record[i-1]+1);


Log in to reply
 

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