线上OJ:
一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=1959 (opens in a new tab)
AcWing:https://www.acwing.com/problem/content/description/453/ (opens in a new tab)
洛谷:https://www.luogu.com.cn/problem/P1077 (opens in a new tab)
核心思想:
1、这是一道 动态规划DP 的题目,问的是**给定n种花,摆出m盆的方案总数
**。
2、由于原文中提到“摆花时 同一种花放在一起,且 不同种类的花 需 按标号 的从小到大的 顺序 依次 摆列” 也就是类似 “1112233344” 这种排法,故本题中不涉及到排列组合问题
。我们设 为给 前 i 种花,共 摆放 j 盆时的方案总数,则最终要求结果就是 f[n][m]。
3、很明显,f[i][j] 是从 前 i-1 种花的方案推导过来的。如果 第 i 种花的数量是 k 盆,则 前 i-1 种花摆放的数量就是 j-k 盆。所以
💡
4、注意初始化 。 表示前 i 种花,摆放0盆的方案数是1
,就是都不摆。初始化时要从f[0][0]开始,否则f[1][1]数据会出错
题解代码:
解法一、动态规划
解法一、动态规划:
#include <bits/stdc++.h>
#define MOD 1000007
using namespace std;
const int N = 105;
int n, m;
int a[N], f[N][N]={0}; // a[i]表示第i种花最多多少盆; f[x][y]记录前i种花,摆放了共j盆的方案数
/* 核心思想:动态规划,f[i][j] 从前面的 f[i-1][j-k] 传递过来。
故设 f[i][j] 表示前i种花,摆放了共j盆的方案数
*/
int main()
{
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 0; i <= n; i++) f[i][0] = 1; // 前i种花,摆放0盆的方案数是1,就是都不摆。初始化时要从f[0][0]开始,否则f[1][1]数据会出错
for(int i = 1; i <= n; i++) // 前i种花
for(int j = 1; j <= m; j++) // 共拜访了j盆, j<=m
for(int k = 0; k <= min(a[i], j); k++) // 第i种花摆放了k盆,k<=m,k<=a[i],则前i-1种花摆放了j-k盆
f[i][j] = (f[i][j] + f[i-1][j-k]) % MOD; // 方程
cout << f[n][m]; // 从第 1 种花要摆放 m 盆开始深搜
return 0;
}