洛谷—P1077 摆花（动态规划入门）

解题思路：

定义状态方程dp[i][j]为前i种花盆摆放j个的总方案数

代码：

#include<iostream>
using namespace std;
const int k = 1000007;
int m, n, arr[110],dp[110][110];
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		cin >> arr[i];
	dp[0][0] = 1;
	for(int i=1;i<=n;++i)
		for (int j = 0; j <= m; ++j)
		{
			for (int l = 0; l <= j && l <= arr[i]; ++l)
				dp[i][j] = (dp[i][j] + dp[i - 1][j - l]) % k;
		}
	cout << dp[n][m];
	return 0;
}