问题
5可以写成以下6种加法之和：
4 + 1 3 + 2 3 + 1 + 1 2 + 2 + 1 2 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1
那么请问100可以写成多少种至少两个整数的加法之和？
* 传送门
分析
这题看起来很简单，但是如果单从加法的角度入手考虑的话，就会发现很容易被误导、被带偏认为是个树形问题。但实际上并不是树形问题，应该说，甚至不是一个只应考虑加法的问题。以题目例子举例，其实我们也可以将5看作为以下6种表达式之和：
四 + 一 三 + 二 三 + 2*一 2*二 + 一 二 + 3*一 5*一
可以看到，我特意将数字本身以中文的方式写出来、将数字的个数以阿拉伯数字的方式写出来。为什么要这样写呢？假设中文数字代表货币面值，那么上面就是用面值【一二三四】元组成【五】元的所有情况。这就让我想起其实以前已经碰到过一模一样的题目了，就是《问题31》。而对于本题的目标100本身，就相当于所有小于100的正整数都是面值货币。查看《问题31》就会知道，面值越多、暴力搜索空间越大。所以本题应该直接用递归或者动态规划的方式来求解。
答案
// answer: count down with dynamic programming
const start = Date.now()
const coins = [], target = 100
for (let i = 1; i < target; ++i)
coins.push(i)
function count_down(money) {
const counts = new Array(money + 1)
counts[0] = 1
counts.fill(0, 1)
for (const coin of coins)
for (let i = coin; i <= money; ++i)
counts[i] += counts[i - coin]
return counts[money]
}
const result = count_down(target)
alert(result + ', ' + (Date.now() - start) + 'ms')
由 bruce 于 2020-06-8 18:38 更新
