【題解】CSES Dice Combinations

題目連結

https://cses.fi/problemset/task/1633

題目簡述

輸入n，請輸出骰子(1~6)加總為n的方法數。
例如：n=3，答案為4，因為 {1,1,1}, {1,2}, {2,1}, {3}。
※答案要 mod (10^9+7)。
※1 ≤ n ≤ 10^6

解題方法

DP。

C++程式碼

#include <iostream>
using namespace std;
int dp[1000001];
int main(){
    int n, mod=1e9+7;
    cin >> n;
    dp[0] = 1; //only 1 step
    for(int i=1; i<=n; i++){ //dp[1~n]
        for(int j=1; j<=6; j++){ //dp[3]=dp[3-1]+dp[3-2]+dp[3-3]
            if(j>i) break; //j<=i
            dp[i] = (dp[i] + dp[i-j]) % mod;
        }
    }
    cout << dp[n] << '\n';
}