My first try with dynamic programming and it works for me! only 92 ms with 30000+ int


  • 0
    K
    class Solution {
    public:
        int numSquares(int n) {
            int srt = (int)sqrt(n);
            
            static int table[35535] = { };
            if(table[n] != 0) return table[n];
            if(srt * srt == n) 
            {
                table[n] = 1;
                return 1;
            }
            else
            {
                int result = 1 + numSquares(n - srt * srt);
                for(int i = srt - 1; i > 0; i--){
                    int temp = numSquares(n - i * i) + numSquares(i * i);
                    if(temp < result) result = temp;
                }   
                table[n] = result;
                return result;
            }
            
        }
    };

Log in to reply
 

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