题解：AcWing 4181 数的划分

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AcWing：4181. 数的划分 - AcWing题库

【题目描述】

将整数n nn分成k kk份，且每份不能为空，问有多少种不同的分法。

当n = 7 , k = 3 n=7,k=3n=7,k=3时，下面三种分法被认为是相同的：( 1 , 1 , 5 ) , ( 1 , 5 , 1 ) , ( 5 , 1 , 1 ) (1,1,5),(1,5,1),(5,1,1)(1,1,5),(1,5,1),(5,1,1)。

【输入】

一行两个整数n , k n,kn,k。

【输出】

一行一个整数，即不同的分法数。

【输入样例】

7 3

【输出样例】

4

【算法标签】

#线性DP-一维#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intn,k;// n: 要划分的整数, k: 划分的部分数intdp[205][10];// dp[i][j]: 将整数i拆分为j个正整数相加的方案数intmain(){cin>>n>>k;// 输入整数n和部分数k// 动态规划初始化dp[0][0]=1;// 将0划分为0个正整数有一种方案// 动态规划计算for(inti=1;i<=n;++i)// 遍历要划分的数i{for(intj=1;j<=k&&j<=i;++j)// 遍历划分的部分数j{dp[i][j]=dp[i-1][j-1]+dp[i-j][j];}}cout<<dp[n][k];// 输出将n划分为k个正整数的方案数return0;// 程序正常结束}

【运行结果】

7 3 4