本题为典型的动态规划：设 f(n) 为用 1 或 2 的若干个数按顺序恰好凑成 n 的方案数。 最后一步若取 1，则前面需凑出 n−1；若取 2，则前面需凑出 n−2。因此有
f(n)=f(n−1)+f(n−2),n≥2边界：
f(0)=1 (空和),f(1)=1 (1)这正是斐波那契转移，且 f(n)=Fn+1（用 F0=0,F1=1 记法）。
实现要点：
dp[0..n]，初始化 dp[0]=1, dp[1]=1；i=2..n，转移 dp[i]=dp[i-1]+dp[i-2]；dp[n]。# 动态规划：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()
// 动态规划：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();
}
}
// 动态规划：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)
4
5