问题描述：
小初喜欢数列，其中特别喜欢 m 数列
所谓 m 数列，就是数列中所有数字和为 m 的数列.
小初热衷于计算 m 数列的个数，但是没有限制的 m 数列的个数是无穷无尽的.
因此小初会再加上一些限制：他希望这个 m 数列的长度为 n ，且数列第 i 个数应该是一个不超过 ai 的非负整数。
小初希望你也能感受到 m 数列的魅力，因此他想你数一数有这样限制的 m 数列有几个。
虽然有许多限制，但是这样的 m 数列可能仍然有很多，因此你只需要求出符合条件的 m 数列个数对 1000007 取模的结果。
输入描述：
第一行包含两个正整数 n 和 m ，中间用一个空格隔开。
第二行有 n 个整数，每两个整数之间用一个空格隔开，依次表示 a1,a2,a3…an-1,an
0 < n <= 100,0 < m <= 100,0 <= ai <= 100
输入描述：
输出格式
一个整数，表示有多少个 数列。注意：因为个数可能很多，请输出个数对
取模的结果。
示例：
输入 #1
2 4
3 2
输出 #1
2
输入 #2
3 5
1 2 3
输出 #2
3
思路:这种题我一般将其看作 m 个球放 n 个桶的球桶组合问题,但是这里有个 ai 的限制条件和允许空桶,需要稍加转换.
dp(i,j)表示 j 个球放 i 个桶的放法.
当前 i 桶可以不放球,放1个球,放两个球…最多放 ai 个球.
那么 i-1 个桶中,就是放 j 个球, j-1 个球, j-2 个球, j-ai 个球.
dp(i,j) = dp(i-1,j) + dp(i-1,j-1) + dp(i-1,j-2) +…+ dp(i-1)(j-ai).
再优化,由上式可得
dp(i,j-1) = dp(i-1,j-1) + dp(i-1,j-2) + … + dp(i-1,j-ai) + dp(i-1,j-1-ai).
合并
dp(i,j) = dp(i-1,j) +dp(i,j-1) – dp(i-1,j-1-ai).
至此,状态转移方程出来了.
#include <algorithm>
#include <cstdio>
using namespace std;
const int mod = 1e6 + 7;
int dp[105][105], a[105];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
//主要是dp(0,0)要为1
//没有球放,不放球一种方法
if (j == 0) {
dp[i][j] = 1;
continue;
}
//没有桶
if (i == 0) {
dp[i][j] = 0;
continue;
}
//防止越界,当前只有3个球,ai为5
//显然最后也只有3个球可以放,其实此时ai就是3.
int tmp = min(j, a[i]);
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
//j-tmp必然>=0
if (j - tmp - 1 >= 0) {
dp[i][j] = (dp[i][j] - dp[i - 1][j - tmp - 1] + mod) % mod;
}
}
}
printf("%d", dp[n][m]);
return 0;
}