[luogu] P1077 擺花

題目詳情

題目分析：

非常經典的動态規劃，dp[i][j]表示從第一種花到第i種花一共j盆花的方法數。

我們知道狀态轉移方程：

d p [ i ] [ j ] = ∑ k a i d p [ i − 1 ] [ j − k ] dp[i][j] = \displaystyle \sum^{a_i}_{k}{dp[i - 1][j - k]} dp[i][j]=k∑ai​​dp[i−1][j−k]

代碼如下：

#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, a[111], dp[111][111];
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    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]); k++)
                dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % 1000007;
    printf("%d\n", dp[n][m]);
}
           

我們仔細觀察發現1~i - 2完全沒用，我們可以把動态規劃數組轉換成一維。也就變成了01背包問題。

代碼如下：

#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, dp[111], a[111];
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    dp[0] = 1;//dp[i]表示i盆花一共dp[i]種方法。
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= 0; j--)
            for (int k = 1; k <= min(a[i], j); k++)
                dp[j] = (dp[j] + dp[j - k]) % 1000007;
    printf("%d\n", dp[m]);
}
           

此外我們還可以用記憶化搜尋的方法。