2017-09-03 82 views
0

嘗試用遞歸解決這個problem但輸入7168得到錯誤的答案。完美的正方形leetcode丟失遞歸解決方案的測試用例

給定一個正整數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.請不要建議替代方法來解決這個問題,因爲我已經嘗試過它們,它的工作原理。我在這裏只是知道這個邏輯的問題。

+1

添加打印到頂部方法:'print(n,result,dp)'。運行它的一小部分(例如12),看看你正在記憶的值。他們對我來說似乎是錯誤的:例如'{2:4,3:4,5:6,...}'。那是你打算做什麼的?通常情況下,你想記住正確的答案:例如'{2:2,3:3,4:1等]'。也許我不明白你的算法。 – FMc

+0

那麼什麼是7168的最佳四項分解(你的代碼沒有找到)? – NPE

+0

@NPE(80,16,16,16) –

回答

1

首先,你有一個錯字:m應該large_no

但是你錯誤地使用了dp:你應該緩存最小的方式來寫i作爲平方和,但你實際上緩存了你碰巧到達的任何路徑的結果。

這意味着你可能會緩存一個意外的大於必要值的值,並且你的算法是錯誤的。雖然算法是錯誤的,但7168是第一個產生錯誤結果的值。

result參數,改變return result+1return 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] 
+0

如果dp [i]代表達到i的最小平方,其中j從1開始到i的平方根,則遞歸關係是相同的:dp [i] = min(1 + dp [i-j * j])。 –

1

我認爲問題在於您將result傳遞給您的遞歸,但不要在記憶中考慮它。

recursive(X, Y, dp)recursive(X, Z, dp)都分別返回dp[X]如果X in dp但返回dp[X] + ydp[X] + z,如果dp[X]尚未memoized(其中y = R - Yz = R - Z,與Rdp[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 
+0

這很有幫助,但因爲(我的方法)超時,所以無法將此答案標記爲正確。 –

+0

sys.setrecursionlimit(10000)當它設置它修復問題並正確地回答它4。 –