Leetcode第279题使用回溯法超时

Question

class Solution {
    
    private int min;
    private int count;
    
    public int numSquares(int n) {
        if (n == 0 || n == 1)
            return n;
        
        min = n;
        count = 0;
        helper(n,count);
        return min;
    }
    
    private void helper(int remaining, int count){
        if ( remaining == 0){
            if (count < min)
                min = count;
        }
        
        for (int i = 1; i * i <= remaining; i ++){
            count ++;
            helper(remaining - i * i, count);
            count --;
        }
    }
}

老师你好，我使用回溯法去解了一下279-LeetCode，但是超时了，我测试了几个input，都得到了准确答案，所以我想我的解法应该是没有问题的，或许可能存在可以优化的地方？我使用的语言是java。

顺便问一下这道题用回溯法的时间复杂度是多少？我猜想是O(logn*log(n))，不知道对吗

Answer 1

liuyubobobo 2019-05-24 01:26:07

279用回溯是超时的。可以继续往后看，在将动态规划的时候，我会介绍记忆化搜索。这个代码很容易修改成记忆化搜索，就不会超时了。

这个问题严格的时间复杂度分析有些复杂。如果对此感兴趣，建议看算法导论中”主定理“一节，在详细地描述递归算法的复杂度分析。不过通常，面试不会用到。大体上，这个算法基本是O(n!)这个级别，注意，有一个叹号，是阶乘级别的。为什么，因为搜索过程中有大量重复。

你可以尝试一下，在本地运行，传入100甚至1000，看看需要多少时间（非常非常长！）然后分析一下，为什么会用这么长的时间？你可以在helper中，对remain进行打印输出，然后用一个更小的数字实验，你就会看到，helper处理了大量的重复值的计算。这些在动态规划一章我都会讲，学到了那里，再回头看，也不迟：）

继续加油！：）