前言

具体代码请在题解区查看

摆花问题题解

题意

题目描述

小明要在花店门口摆放$m$盆花，共有$n$种花。

每种花最多摆放$a_{i}$盆，且同种花必须放在一起，不同种类花要按照编号顺序摆放。

要求计算所有可能的摆放方案数，结果对$10^6+7$取模。

测试用例分析

输入样例1：‌

2 4
3 2

输出样例1：‌

2

分析：‌

有$2$种花 共摆放$4$盆

第$1$种花最多$3$盆$(a_{1}=3)$ 第$2$种花最多$2$盆$(a_{2}=2)$

可能的方案：

其他组合要么超过限制，要么总数不足$4$盆

解题思路

1.40wa的做法

记录

可以使用递归枚举所有可能的摆放组合：

对于每种花，尝试摆放$0$到$a_{i}$盆

确保总盆数不超过==$m$==

当所有花都考虑完后，如果总盆数正好是$m$，则方案数$+1$

代码

这种方法时间复杂度为高，当$n$和$a_{i}$较大时会超时。

动态规划解法(100ac的解法)

使用动态规划来优化：

定义$dp[i][j]$表示前i种花摆放j盆的方案数

状态转移方程：

初始条件：$dp[0][0] = 1$ 最终答案：$dp[n][m]$

这种方法时间复杂度为$O(nm*max_a)$，空间复杂度$O(nm)$

代码实现