蓝桥杯2021年第十二届真题第二场-整数分解

题目

【问题描述】 将 3 分解成两个正整数的和，有两种分解方法，分别是 3 = 1 + 2 和3 = 2 + 1。注意顺序不同算不同的方法。 将 5 分解成三个正整数的和，有 6 种分解方法，它们是 1+1+3 = 1+2+2 =1 + 3 + 1 = 2 + 1 + 2 = 2 + 2 + 1 = 3 + 1 + 1。 请问，将 2021 分解成五个正整数的和，有多少种分解方法？

【答案提交】 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

题解

动态规划或组合数。

动态规划比较简单。

组合数，挡板法，把2021想象成2021个1，每个1之间有2020个空，我们的目的是插入四个板子将这2021个数分成五组，每一组1之和就是作为一个加数，所以 C 2020 4 C_{2020}^4 C20204​就是我们的答案。

组合数排列数的实现代码

代码 动态规划

#include
using namespace std;

long long dp[10][3000]; // dp[i][j] 用i个数表示出j的方案数 

int N = 5, M = 2021;

int main()
{
	for (int j = 1;j