整数划分问题
集合分析:
集合:总数为i,且划分个数为j的所有情况;
属性:count
把每种情况分成有0和无0两种情况分类集合:
有0,直接f[i][j-1]把上一种情况直接拿过来
无0,说明都大于等于1,那么直接全部减去一,把上面所对应的状态拿过来加一就是这种状态f[i-j][j]
核心:数学的映射思想
#include<iostream>
#define N 11
using namespace std;
//整数划分问题
int f[N][N];
int main()
{
int t;
cin>>t;
while(t --)
{
int m,n;
cin>>m>>n;
f[0][0] = 1;
for(int i = 0;i <= m;i ++)
for(int j = 1;j <= n;j ++)
{
f[i][j] = f[i][j-1];
if(i >= j) f[i][j] += f[i-j][j];
}
cout<<f[m][n]<<endl;
}
return 0;
}