CSES – Dice Combinations

題目連結

題意

給一個 n，你可以骰一個骰子一次或一次以上，問有幾種方法點數加起來剛好等於 n。

解題想法 – DP

狀態

dp[i] 表示要骰出總和 i 有幾種方法

轉移

for j = 1 ~ 6:
    dp[i] += dp[i-j];

對於每個 i ，我們可以枚舉他上一步骰了 1 還是 2, 還是 3…。
假如上一步骰了 1 的話，就代表我們是從 dp[i-1] 過來的。
假如上一步骰了 2 的話，就代表我們是從 dp[i-2] 過來的。
…. 以此類推

我們可以把全部的可能加起來!

初始條件

dp[0] = 1

因為要骰出 0 只有一種方法，就是都不骰，不骰也算是一種方法!

複雜度: O(n)

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9+7;
int main(){
    int n;
    cin >> n;
    vector <long long> dp(n+1);
    dp[0] = 1;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= 6 && i-j >= 0;j++){
            (dp[i] += dp[i-j]) %= MOD;
        }
    }
    cout << dp[n] << '\n';
}