C++实现可重复用1和2求和的组合数计算（求非递归方案）

问题分析 #

你要计算的是排列数（示例中1+2和2+1视为不同情况），这个问题可通过动态规划解决，核心规律清晰：

• 对目标总和n，最后一步只能是加1或加2：
  • 若最后一步加1，前面的总和为n-1，所有n-1的排列都可在末尾加1得到n的排列
  • 若最后一步加2，前面的总和为n-2，所有n-2的排列都可在末尾加2得到n的排列
• 递推公式：f(n) = f(n-1) + f(n-2)
• 初始条件：
  • f(1) = 1（仅[1]一种）
  • f(2) = 2（[1,1]、[2]两种）

非递归实现思路 #

采用迭代从底向上计算，既避免递归的栈开销，又自然处理数字可重复使用的逻辑——每一步计算都基于前面的结果，相当于重复利用1和2构建新排列。

伪代码 #

function countPermutations(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 2
    prev_prev = 1  # 对应f(n-2)的初始值f(1)
    prev = 2       # 对应f(n-1)的初始值f(2)
    current = 0
    for i from 3 to n:
        current = prev + prev_prev
        prev_prev = prev
        prev = current
    return current

C++ 实现代码 #

#include <iostream>
using namespace std;

long long countPermutations(int n) {
    if (n <= 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    long long prev_prev = 1; // 存储f(n-2)的值
    long long prev = 2;      // 存储f(n-1)的值
    long long current = 0;
    for (int i = 3; i <= n; ++i) {
        current = prev + prev_prev;
        prev_prev = prev;
        prev = current;
    }
    return current;
}

int main() {
    int target;
    cout << "请输入目标总和: ";
    cin >> target;
    cout << "排列数为: " << countPermutations(target) << endl;
    return 0;
}

可重复使用数字的逻辑解释 #

递推过程本身就支持重复使用1和2：

• 计算f(n)时，f(n-1)包含所有以1结尾的排列，其前置部分可包含任意数量的1和2；f(n-2)包含所有以2结尾的排列，前置部分同理
• 每一步都可自由选择添加1或2，不受之前使用次数的限制，自然实现了数字的可重复利用

常见思路瓶颈解决 #

如果之前有以下困惑，可对应解决：

• 混淆组合与排列：若要求组合（1+2和2+1算一种），公式为(n/2)+1，但你的示例明确是排列，所以用上述斐波那契式递推
• 递归栈溢出/效率低：非递归迭代的时间复杂度为O(n)，空间复杂度为O(1)，完全规避递归的性能问题
• 不知道如何建模重复使用：递推的每一步选择独立，无需额外处理重复，直接通过前置结果累加实现重复利用

内容的提问来源于stack exchange，提问作者Joe Nibali