python - 完美正方形 leetcode 缺少带有递归解决方案的测试用例

Question

试图解决这个问题 problem使用递归但输入 7168 得到错误答案。

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

def recursive(self, n, result, dp):
    if n in dp:
        return dp[n]
    #very large number
    large_no = 1 << 31
    if n < 1:
        return 0      
    #checking if n is a square or not?  
    r = n**0.5
    if int(r)*int(r) == n:
        return result + 1 
    #iterate from square root till 1 checking all numbers
    r = int(r)
    while r >= 1:
        large_no = min(large_no, self.recursive(n - int(r)*int(r), result + 1, dp))
        r -= 1
    #memoize the result
    dp[n] = large_no
    return large_no

我这样调用上面的函数:self.recursive(7168, 0, {})

答案应该是 4，但我得到了 5。请不要建议解决此问题的替代方法，因为我已经尝试过它们并且有效。我来这里只是为了了解这种逻辑的问题。

Answer 1

首先，你有一个错字:m 应该是 large_no。

但您使用的 dp 不正确:您应该缓存将 i 写为平方和的最小方法，但实际上缓存的结果是无论您碰巧到达那里的路径。

这意味着您可能意外地缓存了一个比必要值更大的值，并且您的算法是错误的。虽然算法是错误的，但 7168 是它产生错误结果的第一个值。

删除 result 参数，将 return result+1 更改为 return 1 并且递归调用:

large_no = min(large_no, 1+self.recursive(n - int(r)*int(r), dp))

代码的清理、工作版本:

def recursive(n, dp):
    if n in dp:
        return dp[n]
    if n == 0: return 0
    best = n
    for r in xrange(int(n**0.5), 0, -1):
        best = min(best, 1 + recursive(n - r*r, dp))
    dp[n] = best
    return dp[n]