解题思路

• 本题要求用若干个数 1、2、3 相加，按顺序恰好得到 $n$ 的方案数，顺序不同视为不同方案（如 $1+2$ 与 $2+1$ 不同）。

• 设 $f(n)$ 为答案，考虑最后一步取值：

  • 若最后取 1，则前面需凑成 $n-1$，方案数为 $f(n-1)$；
  • 若最后取 2，则前面需凑成 $n-2$，方案数为 $f(n-2)$；
  • 若最后取 3，则前面需凑成 $n-3$，方案数为 $f(n-3)$。

• 因此得到动态规划递推式（“三项斐波那契”）：

  $$f(n)=f(n-1)+f(n-2)+f(n-3),\qquad n\ge 3$$

• 边界条件（可直接列举）：

  

复杂度分析

• 时间复杂度：$O(n)$，单次线性递推。
• 空间复杂度：$O(n)$

代码实现

Python

# 动态规划：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
# 边界：dp[0]=1, dp[1]=1, dp[2]=2
# 说明：当 n ≤ 72 时，答案不超过有符号 64 位范围
import sys

def count_ways(n: int) -> int:
    if n == 0:
        return 1
    if n == 1:
        return 1
    if n == 2:
        return 2
    dp = [0] * (n + 1)
    dp[0], dp[1], dp[2] = 1, 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
    return dp[n]

def main():
    data = sys.stdin.read().strip().split()
    n = int(data[0])  # 默认输入合法
    print(count_ways(n))

if __name__ == "__main__":
    main()

Java

// 动态规划：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
// 边界：dp[0]=1, dp[1]=1, dp[2]=2
// 说明：当 n ≤ 72 时，答案在 long 范围内
import java.util.Scanner;

public class Main {
    // 外部函数：计算方案数（long，满足 n≤72 的要求）
    static long countWays(int n) {
        if (n == 0) return 1L;
        if (n == 1) return 1L;
        if (n == 2) return 2L;
        long[] dp = new long[n + 1];
        dp[0] = 1L; dp[1] = 1L; dp[2] = 2L;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; // 三项递推
        }
        return dp[n];
    }

    // 主函数：ACM 风格输入输出
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();   // 默认输入合法
        System.out.println(countWays(n));
        in.close();
    }
}

C++

// 动态规划：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
// 边界：dp[0]=1, dp[1]=1, dp[2]=2
// 说明：当 n ≤ 72 时，答案在 long long 范围内
#include <bits/stdc++.h>
using namespace std;

// 外部函数：计算方案数（long long，满足 n≤72 的要求）
long long countWays(int n) {
    if (n == 0) return 1LL;
    if (n == 1) return 1LL;
    if (n == 2) return 2LL;
    vector<long long> dp(n + 1, 0LL);
    dp[0] = 1LL; dp[1] = 1LL; dp[2] = 2LL;
    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; // 三项递推
    }
    return dp[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;  // ACM 风格输入
    cout << countWays(n) << "\n";
    return 0;
}

题面描述

本题在“每次取 1 或 2 凑成 $n$”的基础上做进一步扩展，给定一个非负整数 $n$。每次可取数 1、2 或 3，将若干个数相加恰好得到 $n$。两种方案只要在某个位置取的数不同，就视为不同（即顺序有区分）。求不同方案数。

记答案为 $f(n)$。

输入格式

• 第一行一个整数 $n$。

输出格式

• 输出一行一个整数：$f(n)$。

数据范围

• $0 \le n \le 60$

样例

样例输入

4

样例输出

7

说明

• 对于 $n=4$，所有顺序不同的分解（每次只能取 1、2、3）共有 7 种，分别是：

1. $1+1+1+1$
2. $1+1+2$
3. $1+2+1$
4. $2+1+1$
5. $2+2$
6. $1+3$
7. $3+1$