Why does DFS+Cache result in Time Limit Exceeded?


  • 0
    Z
    class Solution {
    public:
        int f(int n, unordered_map<int, int>& cache) {
            if (n == 1) {
                return 1;
            }
            if (n == 0) {
                return 0;
            }
            if (cache.find(n) != cache.end()) {
                return cache[n];
            }
            auto min = 10000000;
            for (auto i = 1; i * i <= n; ++i) {
                auto tmp = f(n - i*i, cache);
                min = (1 + tmp) < min ? (1 + tmp) : min;
            }
            cache[n] = min;
            return min;
        }
        int numSquares(int n) {
            unordered_map<int, int> cache;
            f(n, cache);
            return cache[n];
        }
    };
    

    AFAIU, this should cost pretty much the same time with the DP solution(both are O(n^2)). Why TLE though?


  • 0
    H

    It really depends on the unordered_map implementation. I'm guessing unordered_map is a hash table. Depends on different collision strategies, it's hard to guarantee O(1) time both accessing and searching a none existing element. Replacing the unordered_map with array will give you an acceptable runtime.


  • 0
    N

    I solved this problem just like you but added one more constraint. I keep tracked what is the min value so far and if I calculated f(n) , will it be more than that or not. It save me sometime and accepted. Though the run time is not that good.


Log in to reply
 

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