蓝桥杯算法提高VIP-摆花-题解（Python代码）动态规划计数问题

解题思路:
    动态规划计数问题。开二维列表dp[i][j]、i代表花的种类，j表示花的数量。mvs表示第i种花的放置最大数量

    确定状态：①最后一步：也就是后摆满的状态是第n种花num[n]盆或者用了num[n]-1依次类推到没用第n种花。

                     ②子问题：也就是那么就是f[n-1][m-0]到f[n-1][m-num[i]]。

    状态转移方程：f[i][j]=∑f[i-1][j-k] (k从0到num[i],且j>=k)

    初始条件与边界问题：

                    ①初始条件：当花的种类只有一种时无论几盆花都只有一种摆法也就是f[1][0~num[1]]都为1

                                         当只能摆放0盆花时，摆放的方法也是一种也就是什么都不摆、所以f[1~i][0] = 1。

                    ②边界问题：索引别越界

    计算顺序：由转移方程很容易看出从小到大计算。

    开始写代码。

参考代码:

n,m = map(int,input().split())
mvs = list(map(int,input().split()))
dp = [[0]*(m+1) for _ in range(n+1)]
for j in range(mvs[0]+1):
    dp[1][j] = 1
for i in range(1,n+1):
    dp[i][0] = 1
for i in range(2,n+1):
    for j in range(1,m+1):
        for k in range(mvs[i-1]+1):
            if j-k>=0:
                dp[i][j] = (dp[i][j]+dp[i-1][j-k])%1000007
print(dp[n][m])