条件组合与排列：如何计算n层建筑中可建造的公寓组合数（大公寓2层、小公寓1层）

嘿，这个问题本质是个经典的递推数列问题，咱们一步步拆解清楚：

核心思路：递推关系 #

假设用 f(n) 表示n层建筑的公寓组合总数，咱们可以从最后一层的选择倒推：

• 如果最后建的是小公寓（占1层），那前面的n-1层的组合数就是 f(n-1)
• 如果最后建的是大公寓（占2层），那前面的n-2层的组合数就是 f(n-2)

因为这两种情况互斥且覆盖所有可能，所以递推公式就是：
f(n) = f(n-1) + f(n-2)

初始条件 #

咱们得先确定基础情况的数值，才能启动递推：

• 当 n=0（空建筑）：可以认为是1种“空组合”，方便递推计算，所以 f(0)=1
• 当 n=1：只能建1个小公寓，所以 f(1)=1
• 当 n=2：有两种选择——两个小公寓，或者一个大公寓，所以 f(2)=f(1)+f(0)=1+1=2

验证示例 #

咱们用几个小数值验证一下：

• n=3：f(3)=f(2)+f(1)=2+1=3，对应的组合是：小+小+小、小+大、大+小，确实3种
• n=4：f(4)=f(3)+f(2)=3+2=5，对应的组合是：小×4、小×2+大、大+小×2、小+大+小、大×2，正好5种

实用计算方式 #

如果n比较大，递归会有大量重复计算，效率很低，所以推荐用迭代的方式从底往上计算：

def count_apartment_combinations(n):
    if n < 0:
        return 0  # 层数不能为负
    elif n == 0:
        return 1
    a, b = 1, 1  # a对应f(0), b对应f(1)
    for _ in range(2, n + 1):
        a, b = b, a + b  # 每次迭代更新为f(k-1)和f(k)
    return b

额外说明 #

这个数列其实就是斐波那契数列的变种——常规斐波那契数列通常定义为 F(1)=1, F(2)=1, F(3)=2，而这里的 f(n) = F(n+1)，比如 f(1)=1=F(2)，f(2)=2=F(3)，本质是同一个数列的不同起始索引而已。

内容的提问来源于stack exchange，提问作者Rashmi Jagadeesh