1.dp分析
因为 2 1 1 和 1 2 1 是一种情况,不考虑顺序,所以可以想到完全背包问题。可以转化为给定一个容量为m的背包,物品重量为0,1,2,3…,每个物品可以选无限次
状态计算:
1.左边情况:最小值为0
那么可转化为总和还为i,只不过少了一个数的情况,即f[i][j - 1]
2.右边情况:最小值大于0
因为最小值大于0,所以每一项都大于等于1。我么可以利用映射,将每一项都减去1,得到的情况是每一项都大于0,这种方案的方案数和映射前是相同的,即f[i][j] = f[i - j][j](有j项,每一项都减去1,就是减去j)
本题和 Acwing 900:整数划分问题类似(算法基础课——计数类dp)
2.代码实现
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 11;
int t, n, m;
int f[N][N];
//f[i][j]表示所有总和为i,且分成j个数的方案
int main()
{
cin >> t;
while(t --)
{
cin >> m >> n; //注意本题先读入m,再读入n
f[N][N] = {0};
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;
}