完美的正方形leetcode丢失递归解决方案的测试用例

Question

尝试用递归解决这个problem但输入7168得到错误的答案。

给定一个正整数n，求出与n和的完美平方数（例如，1,4,9,16，...）的最小数。例如，给定n = 12，返回3，因为12 = 4 + 4 + 4;给定的n = 13，返回2，因为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] 

Answer 2

我认为问题在于您将result传递给您的递归，但不要在记忆中考虑它。

recursive(X, Y, dp)和recursive(X, Z, dp)都分别返回dp[X]如果X in dp但返回dp[X] + y和dp[X] + z，如果dp[X]尚未memoized（其中y = R - Y和z = R - Z，与R当dp[X]得到memoized的result值）。

我会摆脱result干脆：

def recursive(self, n, 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 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), dp)) 
     r -= 1 
    #memoize the result 
    dp[n] = large_no + 1 
    return large_no + 1