c - 我真的不知道从哪里开始

Question

通过使用 1 到 9 的 9 个数字，您应该找到使用乘法和加法得到 N 的方法的数量。

例如，如果给出 100，您将回答 7。

原因是有 7 种可能的方法。

100 = 1*2*3*4+5+6+7*8+9

100 = 1*2*3+4+5+6+7+8*9

100 = 1+2+3+4+5+6+7+8*9

100 = 12+3*4+5+6+7*8+9

100 = 1+2*3+4+5+67+8+9

100 = 1*2+34+5+6*7+8+9

100 = 12+34+5*6+7+8+9

如果这个问题给你，你会如何开始？

Answer 1

我们可以使用括号吗？这将大大增加可能性。

我会尝试找到第一个加法项，比如说 1×23。这些术语的数量有限，而且由于我们无法减去，我们知道如果我们得到的术语高于我们的目标，我们可以将其从搜索中删除。这让我们寻找 23 + f = 100 的解，其中 f 是另一个形式完全相同的公式。但这与解决数字 4-9 和目标 77 的原始问题完全相同!因此，递归地调用您的算法，并将该子问题的解决方案添加到原始问题的解决方案中。也就是说，如果我们有 23 + 4，那么数字 5-9 且 n = 73 的子问题是否有解？分而治之。

您可能会受益于部分解决方案的动态表，因为您可能会以不同的方式得到相同的子问题:1+2+3 = 1×2×3，因此用数字 4-9 和目标来解决子问题94 两次重复工作。

根据最受约束的优先原则，从右到左可能比从左到右更好。 89、8×9 或 78+9 为可能的解决方案留下的空间比 1+2+3、1×2×3、12×3、12+3 或 1×23 少得多。