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