DP硬幣找零算法 - 從表

Question

找回硬幣組合要了解我們有多少種方法有可能使變化給定硬幣[1,2,3]量4，我們可以創建產生如下表DP算法：

table[amount][coins.count] 
     0 1 2 3 4 
     ----------- 
(0) 1 | 1 1 1 1 1 
(1) 2 | 1 1 2 2 3 
(2) 3 | 1 1 2 3 4 

最後一個位置是我們的答案。答案是4，因爲我們有以下組合：[1,1,1,1],[2,1],[2,2],[3,1]。

我的問題是，是否有可能從我剛剛生成的表中檢索這些組合？怎麼樣？

爲了完整起見，這裏是我的算法

func coinChange(coins: [Int], amount: Int) -> Int { 
    // int[amount+1][coins] 
    var table = Array<Array<Int>>(repeating: Array<Int>(repeating: 0, count: coins.count), count: amount + 1) 

    for i in 0..<coins.count { 
     table[0][i] = 1 
    } 

    for i in 1...amount { 
     for j in 0..<coins.count { 

      //solutions that include coins[j] 
      let x = i - coins[j] >= 0 ? table[i - coins[j]][j] : 0 
      //solutions that don't include coins[j] 
      let y = j >= 1 ? table[i][j-1] : 0 

      table[i][j] = x + y 
     } 
    } 
    return table[amount][coins.count - 1]; 
} 

謝謝！

-

解決方案

這裏是一個醜陋的功能檢索組合的基礎上，@Sayakiss的解釋：

func getSolution(_ i: Int, _ j: Int) -> [[Int]] { 
     if j < 0 || i < 0 { 
      //not a solution 
      return [] 
     } 
     if i == 0 && j == 0 { 
      //valid solution. return an empty array where the coins will be appended 
      return [[]] 
     } 
     return getSolution(i - coins[j], j).map{var a = $0; a.append(coins[j]);return a} + getSolution(i, j - 1) 
    } 

getSolution(amount, coins.count-1)

輸出：

[[1, 3], [2, 2], [1, 1, 2], [1, 1, 1, 1]]

Answer 1

當然可以。我們爲您的table[i][j]定義了一個新功能get_solution(i,j)這意味着所有解決方案。 你可以認爲它返回一個數組數組，例如，get_solution(4,3)的輸出是[[1,1,1,1],[2,1],[2,2],[3,1]]。然後：

• 案例1.從get_solution(i - coins[j], j)加coins[j]任何解決方案是table[i][j]的解決方案。

• 案例2.get_solution(i, j - 1)的任何解決方案都是針對table[i][j]的解決方案。

你能證明案件1 +案例2是table[i][j]所有可能的解決方案（請注意你table[i][j]通過這種方式）。

唯一的問題仍然是實施get_solution(i,j)，我認爲你自己做這件事很好。

如果您還有任何問題，請不要猶豫，在這裏留下評論。