Why my DP method is slow?


  • 0
    M

    Hi all. I'm using a Dynamic Programming to approach this problem. So the logic is:

    1. We gonna iterate every possible number that n will start to subtract. For example 12, its sqrt is 3, so we gonna check what if 12 minus 3^2 first, what if minus 2^2 first and so on.

    2. For every possible starting number. solution(n) = min (1 + solution(n-i^2), currentResult);

    So I have the following code:

       int numSquaresDP(int n, map<int, int> & memo) {
        if (memo.find(n) != memo.end()) {
            return memo[n];
        }
        else {
            int sqrtN = sqrt(n);
            int result = INT_MAX;
            for (int i = sqrtN; i > 0; i--) {
                int tempResult;
                memo[i*i] = 1;
                if (memo.find(n-i*i) != memo.end()) {
                    tempResult = memo[n-i*i];
                }
                else {
                    tempResult = numSquaresDP(n-i*i, memo);
                    memo[n-i*i] = tempResult;
                }
                result = min(tempResult+1, result);
            }
            memo[n] = result;
            return result;
        }
    }
    
    int numSquares(int n) {
        map<int, int> memo;
        memo[0] = 0;
        return numSquaresDP(n,memo);
    }
    

    It compute the correct number but exceed time limit when n is great. But I have no idea what I did wrong and how should I optimize it to make it become faster. I know by doing some math trick can make this run super fast but I just want to know what I did wrong in my case. Thank you guys in advance!


  • 0

    @mugua-stolaf As for DP solution, you can check my post here, but I suggest the math solution here.


Log in to reply
 

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