題目描述

這里有 d 個一樣的骰子，每個骰子上都有 f 個面，分別標號為 1, 2, ..., f。
我們約定：擲骰子的得到總點數(shù)為各骰子面朝上的數(shù)字的總和。
如果需要擲出的總點數(shù)為 target，請你計算出有多少種不同的組合情況（所有的組合情況總共有 f^d 種），模 10^9 + 7 后返回。

題目解析

這是一個典型的動態(tài)規(guī)劃問題，得到狀態(tài)轉移方程，dp[i][j] = sum(dp[i-1][j-1], dp[i-1], [j-2], ..., dp[i-1][j-k]), 其中i表示為投擲骰子的個數(shù)，j為投擲得到的總點數(shù)，k為骰子的面數(shù)。

C++代碼

    int numRollsToTarget(int d, int f, int target) {
        int mod = 1000000007;
        int dp[31][1001];
        memset(dp, 0, sizeof(dp));
        //邊界起點初始化
        int minX = min(f, target);
        for(int i = 1; i <= minX; i++) {
            dp[1][i] = 1;
        }
        //進行順推過程
        for(int i = 2; i <=d; i++) {
            for(int j = i; j <= i*f; j++) {
                for(int k = 1; k<=f&&j>=k; k++) {
                    dp[i][j] += dp[i-1][j-k];
                    dp[i][j] %= mod;
                }
            }
        }

        return dp[d][target];
    }