解题思路

本题为典型的动态规划：设 $f(n)$ 为用 1 或 2 的若干个数按顺序恰好凑成 $n$ 的方案数。 最后一步若取 1，则前面需凑出 $n-1$；若取 2，则前面需凑出 $n-2$。因此有

边界：

这正是斐波那契转移，且 $f(n)=F_{n+1}$（用 $F_0=0,F_1=1$ 记法）。

实现要点：

• 建立 dp[0..n]，初始化 dp[0]=1, dp[1]=1；
• 循环 i=2..n，转移 dp[i]=dp[i-1]+dp[i-2]；
• 输出 dp[n]。

复杂度分析

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

代码实现

Python

# 动态规划：dp[i] = dp[i-1] + dp[i-2]
# 边界：dp[0]=1, dp[1]=1
import sys

def count_ways(n: int) -> int:
    """返回使用 1/2 按顺序凑成 n 的方案数（n≤45，int 范围）"""
    if n <= 1:
        return 1
    dp = [0] * (n + 1)  # 显式 DP 数组
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # 斐波那契式转移
    return dp[n]

def main():
    # ACM 风格：标准输入读取一个非负整数 n
    data = sys.stdin.read().strip().split()
    n = int(data[0])
    # 题意保证答案在 int 范围内时 n≤45；此处默认输入合法
    print(count_ways(n))

if __name__ == "__main__":
    main()

Java

// 动态规划：dp[i]=dp[i-1]+dp[i-2]，边界 dp[0]=1, dp[1]=1
// 本题范围 n≤45，int 足够
import java.util.Scanner;

public class Main {
    // 外部函数：计算方案数
    static int countWays(int n) {
        if (n <= 1) return 1;
        int[] dp = new int[n + 1]; // 显式 DP 数组
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2]; // 斐波那契转移
        }
        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[0]=1, dp[1]=1；本题范围 n≤45，int 足够
#include <bits/stdc++.h>
using namespace std;

// 外部函数：计算方案数
int countWays(int n) {
    if (n <= 1) return 1;
    vector<int> dp(n + 1, 0); // 显式 DP 数组
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2]; // 斐波那契式转移
    }
    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;
}

题面描述

给定一个非负整数 $n$。每次可取数 1 或 2，将若干个数相加恰好得到 $n$。两种方案只要在某个位置取的数不同，就视为不同（即顺序有区分）。求不同方案数。

记答案为 $f(n)$

输入格式

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

输出格式

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

数据范围

• $0 \le n \le 60$

样例

样例输入

4

样例输出

5

说明

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

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