完美的正方形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