P84. 硬币面值组合问题

https://algocasts.io/episodes/JNmDARGO

有一些問題困擾我啦。比如說 d(i, j) 表示用前 i 種幣組成面值爲 j,那麼 d(i-1, j)d(i, j-coins[i-1]) 是一定不會重複的,這點我是理解的。但是如何證明這兩個式子的可以覆蓋等同於 d(i, j) 意義的值呢。等同于我在問“如何證明此二式的和考慮到了所有情況”。

咦好像不支持公式語法。

@punut

可以使用 markdown 语法。

d(i, j) 表示前 i 种面值的硬币凑成数值 j 的组合数量。你只拿一个关注点来切分:是否要拿下标为 i-1 币值的硬币。回答只有两种:拿和不拿。拿和不拿互为补集,肯定是凑成了解的全集的。

拿的话,我至少就要拿一个,不然会包含不拿的情况。于是要凑的数值变成 j-coins[i-1]。而既然这条路径是可以拿下标为 i-1 币值的硬币,后面肯定也还是可以拿。于是这种情况是 d(i, j-coins[i-1])

不拿的话,我就只能用前 i-1 种面值的硬币来凑数值 j,数量是 d(i-1, j)

所以,这里并不是说我拍脑袋想了两个式子,然后来证明它们组合起来覆盖了所有情况。而是我们先把所有情况分成两种类型(拿和不拿),分完后才去想这两个式子是怎样的。这样去思考,证明这件事也就水到渠成了。

1赞