遞歸硬幣收集在網格中

Question

如何編寫一個遞歸代碼，告訴我可以從網格中收集的最大數量的硬幣，其中每個單元格可能包含或不包含只能向下和向右移動的硬幣？我也必須使用記憶。

ex: [[0,0,1], 
     [0,1,1], 
     [1,0,0]] 

max_coins只移動向下和向右= 2

Answer 1

首先，你需要這個問題背後的遞推關係：如果硬幣在細胞[i][j]的最大數量由C[i][j]表示，則

C[i][j] = max(C[i - 1][j], C[i][j - 1]) + No. of coins on cell[i][j] 

如果你使用這種重現進行編碼，那麼對於不同的單元格來說，相同調用會有很多重複的參數和相同的參數，並且它的複雜性將是指數級的。爲避免這種情況，您可以存儲數組中的中間調用的結果，使用當它們再次需要時。這樣，您只需計算一次單元的值，代碼就會快得多。

因此，首先創建一個二維數組，其中包含您可以在任何單元中擁有的最大硬幣數量，然後使用遞推關係填充適當的值。從上到下，從左到右。