时间戳

首页 > 解决方案 > 完美平方 leetcode - 带记忆的递归解决方案

java - 完美平方 leetcode - 带记忆的递归解决方案

问题描述

试图通过递归和记忆来解决这个问题，但是对于输入 7168，我得到了错误的答案。

    public int numSquares(int n) {
        Map<Integer, Integer> memo = new HashMap();
        List<Integer> list = fillSquares(n, memo);
        if (list == null)
            return 1;
        return helper(list.size()-1, list, n, memo);
    }
    
    private int helper(int index, List<Integer> list, int left, Map<Integer, Integer> memo) {
        
        if (left == 0)
            return 0;
        if (left < 0 || index < 0)
            return Integer.MAX_VALUE-1;
        
        if (memo.containsKey(left)) {
            return memo.get(left);
        }
        
        int d1 = 1+helper(index, list, left-list.get(index), memo);
        int d2 = 1+helper(index-1, list, left-list.get(index),  memo);
        int d3 = helper(index-1, list, left, memo);
        
        int d = Math.min(Math.min(d1,d2), d3);
        memo.put(left, d);
        return d;
    }
    
    private List<Integer> fillSquares(int n, Map<Integer, Integer> memo) {
        int curr = 1;
        List<Integer> list = new ArrayList();
        int d = (int)Math.pow(curr, 2);
        while (d < n) {
            list.add(d);
            memo.put(d, 1);
            curr++;
            d = (int)Math.pow(curr, 2);
        }
        if (d == n)
            return null;
        return list;
    }

我这样打电话：

numSquares(7168)

所有的测试用例都通过了（甚至是复杂的用例），但是这个失败了。我怀疑我的记忆有问题，但无法确定到底是什么。任何帮助将不胜感激。

标签： javaalgorithmrecursiondynamic-programmingperfect-square

解决方案

您拥有由要获得的值作为键的记忆，但这没有考虑 的值index，这实际上限制了您可以使用哪些权力来获得该值。这意味着如果（在极端情况下）index为 0，您只能减少剩下的一个平方 (1²)，这很少是形成该数字的最佳方式。因此，在第一个实例中，memo.set()将注册一个非最佳数量的方格，稍后将由递归树中未决的其他递归调用更新。

如果您添加一些条件调试代码，您会看到多次map.set调用相同的值，并且使用不同的值。left这不好，因为这意味着该if (memo.has(left))块将在该值不能保证是最佳的情况下执行（还）。

index你可以通过在你的记忆密钥中加入来解决这个问题。这增加了用于记忆的空间，但它会起作用。我想你可以解决这个问题。

但是根据拉格朗日的四平方定理，每个自然数最多可以写成四个平方的和，所以返回的值绝不应该是 5 或更多。当您通过该数量的术语时，您可以缩短递归。这降低了使用记忆的好处。

最后，有一个错误fillSquares：当它是一个完美的正方形时，它也应该添加n自己，否则你将找不到应该返回 1 的解决方案。

推荐阅读