algorithm - 不同的方式 int n 可以分成 1 或 2 组

这是向我提出的任务问题：

一个病人有 n 颗药丸要吃。每天，他可以服用一粒或两粒，直到所有的药丸都用完。让 T(n) 表示患者可以服用所有 n 个药丸的不同方式的数量。给出 T(n) 的封闭形式。（请注意 - 例如 - 两个序列 (1, 2, 2) 和 (2, 1, 2) 被视为服用 5 片药丸的两种不同方式。）

我尝试使用 n = 1 到 8 的集合，看看是否能找到这样的模式：

n=1 {1} n=2 {{1,1},{2}} n=3 {{1,1,1},{1,2},{2,1}} n=4 {{1 ,1,1,1},{1,1,2},{1,2,1},{2,1,1},{2,2}} ...

但是一直没办法。n=1-8 的组合是 1,2,3,5,8,12,18,25

有人有想法吗？

标签： algorithmtimetime-complexitycombinatorics

您的示例在 8 之后显示错误值（应该是 13...）。

考虑下一种方法：在最后一天，患者可以吃一粒或两粒（n = (n-1) + 1 或n = (n-2) + 2）。所以组成 T(n) 值的方法数是

T(n) = T(n-1) + T(n-2)

对 T(n-1) 和 T(n-2) 重复相同的过程，您将在 T(0) 或 T(1) 处完成 - 这些值显然等于 1。

所以建立循环序列并解决任何 n 的循环。

请注意，您可以从末尾展开递归（递归方法）并从 0/1 - 迭代方法开始。

当您找到正确的值时，您可能会发现它们形成了著名的序列并阅读了更多相关信息。