[NOIP 2001 提高组] 数的划分

知识点

动态规划、整数划分

解题思路

令f[s][k]表示把s拆成k个正整数且不计顺序的方案数。含1的方案去掉一个1，对应f[s-1][k-1]；不含1的方案把每份减1，对应f[s-k][k]。用f[0][0]=1递推，答案f[n][k]。

正确性说明

两类按最小部分是否为1互斥且穷尽。去掉一个1与给所有部分减1分别是可逆映射，不改变对顺序的忽略，因此递推准确。按总和递增计算，所有依赖已求得。

易错点

每份非空；不把不同顺序重复算；数组越界状态按0处理。

复杂度

时间O(nk)，空间O(nk)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int n,k;cin>>n>>k;long long f[201][7]={};f[0][0]=1;for(int s=1;s<=n;s++)for(int j=1;j<=k;j++){f[s][j]=f[s-1][j-1];if(s>=j)f[s][j]+=f[s-j][j];}cout<<f[n][k]<<'\n';}