本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来,并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构,旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏:算法题解:C++与Python实现!
附上汇总贴:算法竞赛备考冲刺必刷题(C++) | 汇总
【题目来源】
AcWing:279. 自然数拆分 – AcWing题库
【题目描述】
给定一个自然数
N
N
N,要求把
N
N
N 拆分成若干个正整数相加的形式,参与加法运算的数可以重复。
注意:
- 拆分方案不考虑顺序;
- 至少拆分成
2
2
2 个数的和。
求拆分的方案数
m
o
d
2147483648
mod\\ 2147483648
mod 2147483648 的结果。
【输入】
一个自然数
N
N
N。
【输出】
输入一个整数,表示结果。
【输入样例】
7
【输出样例】
14
【算法标签】
#完全背包
【代码详解】
// 朴素做法(MLE)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 4005, mod = 2147483648; // N: 最大n值,mod: 取模数
int n, f[N][N]; // n: 目标和,f[i][j]: 用前i个正整数组合出j的方案数
signed main()
{
cin >> n; // 输入目标和n
// 初始化:用任何数组合出0都只有1种方案(不选任何数)
for (int i = 0; i <= n; i++)
f[i][0] = 1;
// 动态规划:i表示当前使用的最大数,j表示目标和
for (int i = 1; i < n; i++) // 注意这里i<n,实际上使用1到n-1的数
for (int j = 0; j <= n; j++) // 遍历所有可能的目标和
{
f[i][j] = f[i – 1][j]; // 不使用数字i的情况
if (j >= i) // 如果j>=i,可以使用数字i
f[i][j] = (f[i][j] + f[i][j – i]) % mod; // 使用数字i的情况
}
cout << f[n – 1][n] << endl; // 输出用1到n-1组合出n的方案数
return 0;
}
// 降维(AC)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 4005, mod = 2147483648; // N: 最大n值,mod: 取模数
int n, f[N]; // n: 目标和,f[j]: 组合出j的方案数
signed main()
{
cin >> n; // 输入目标和n
// 初始化:组合出0只有1种方案(不选任何数)
f[0] = 1;
// 动态规划
for (int i = 1; i < n; i++) // 遍历使用的数字1到n-1
for (int j = i; j <= n; j++) // 遍历目标和,从i开始
f[j] = (f[j] + f[j – i]) % mod; // 完全背包的优化,使用数字i
cout << f[n] << endl; // 输出用1到n-1组合出n的方案数
return 0;
}
【运行结果】
7
14

![P11246 [GESP202409 六级] 小杨和整数拆分-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108100631-6af049a75855c-220x150.png)
![打卡信奥刷题(3678)用C++实现信奥题 P12274 [蓝桥杯 2024 国 Python B] 设计-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108053830-6af00ad6bdf8d-220x150.png)

