DP Coin Change Algorithm - 从 table 中检索硬币组合

Question

为了找到给定硬币 [1,2,3] 的数量 4 我们有多少种找零的方法，我们可以创建一个 DP 算法来产生以下 table:

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].

我的问题是，是否可以从我刚刚生成的 table 中检索这些组合？怎么样？

为了完整起见，这是我的算法

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 = [=13=]; 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

当然可以。我们定义了一个新函数 get_solution(i,j)，这意味着 为您的 table[i][j] 所有解决方案。你可以认为它是returns一个数组的数组，例如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].[=22 的解=]
情况 2. 来自 get_solution(i, j - 1) 的任何解决方案都是 table[i][j] 的解决方案。

你可以证明情况 1 + 情况 2 是 table[i][j] 的所有可能解决方案（注意你通过这种方式得到 table[i][j]）。

剩下的唯一问题是实施 get_solution(i,j)，我认为您自己来实施比较好。

如果您还有任何问题，请随时在这里发表评论。

DP Coin Change Algorithm - 从 table 中检索硬币组合

DP Coin Change Algorithm - Retrieve coin combinations from table

dynamic-programming

coin-change

swift