上题：

题目描述

小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共m盆。通过调查顾客的喜好，小明列出了顾客最喜欢的n种花，从1到n标号。为了在门口展出更多种花，规定第i种花不能超过ai盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。

试编程计算，一共有多少种不同的摆花方案。

输入

第一行包含两个正整数n和m，中间用一个空格隔开。

第二行有n个整数，每两个整数之间用一个空格隔开，依次表示a1、a2、……an。

输出

输出只有一行，一个整数，表示有多少种方案。

样例输入

2 4
3 2

样例输出

2

本题看到之后就会自然联想到dp

因为前面的花的摆放会影响到后面的花摆放方式

故通过理解

发现了这个状态转移方程

dp[i][j] = dp[i-1][j-0] + dp[i-1][j-1] + dp[i-1][j-2] + ...... + dp[i-1][j-min(a[i], j)]

对于这于方程是这样理解的

前i个位置的花的摆放（包括第i个位置）是由前i-1个位置花的摆放决定的，前i-1个位置的花数量确定了，那么最后一个位置的花的数量也相继确定，所以通过这些循环累加即确定了前i个位置的所以摆放方案。

我们面临这样一个问题，就是上式中的红体部分如何得到的

因为题目中有要求，第i个位置的摆花数量不得超过a[i]个，而前i个位置的数量又不得超过j个

红题部分即第i个位置摆0个，摆1个，摆2个，......摆min(a[i], j)个

摆min(a[i], j)是因为第i个位置最多摆a[i]个，而总共前i个位置只能摆j个，所以第i个位置的最多数量是两者中的较小值。

这里你可能会疑惑如果前i-1个位置的a[1]+...a[i-1] < j改如何，这时候的话这种情况就是不存在的，故我们只需要在状态转移前将其全部初始化为0即可

但是尽量不要用memset初始化二维数组，你可以将数组定义为全局数组，此时会自动初始化为0，或者是在main函数中

​int dp[0][0] = {0};

即可

然后你会发现如果初始化全部都为0了，那怎么状态转移，所有的情况都将是0啊

所以你需要先定义最初的状态，你会发现在第一个位置从0盆到a[1]盆都会只有一种情况

将其都定为1即可。

下面贴个代码：

#include<stdio.h>
#include<string.h>
#define mod 1000007
int _min(int c, int b){
    return c < b ? c : b;
}
int main()
{
    int n, m, i, j, k;
    int dp[105][105], a[105];
    memset(dp, 0, sizeof(dp));
    scanf("%d %d", &n, &m);
    for(i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for(i = 0; i <= a[1]; i++)
        dp[1][i] = 1; 
    for(i = 2; i <= n; i++)
        for(j = 0; j <= m; j++){ 
            int t = _min(a[i], j);
            for(k = 0; k <= t; k++)
                 dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % mod;
        } 
    printf("%d", dp[n][m]);
    return 0;
}

 

ps：C++中#include<algorithm>自带min函数