花店摆花方案计数 - 动态规划算法实现

#include #include using namespace std;

const int MOD = 1000007;

int main() { int n, m; cin >> n >> m; vector a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; }

vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= m; ++j) {
        for (int k = 0; k <= min(j, a[i-1]); ++k) {
            dp[i][j] += dp[i-1][j-k];
            dp[i][j] %= MOD;
        }
    }
}

cout << dp[n][m] << endl;

return 0;

}