题目描述

这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k。

给定三个整数 n，k 和 target，返回可能的方式（从总共 k^n 种方式中）滚动骰子的数量，使正面朝上的数字之和等于 target。

答案可能很大，你需要对 10^9 + 7 取模。

样例

输入：n = 1, k = 6, target = 3
输出：1
解释：你扔一个有 6 张脸的骰子。
得到3的和只有一种方法。

输入：n = 2, k = 6, target = 7
输出：6
解释：你扔两个骰子，每个骰子有 6 个面。
得到 7 的和有 6 种方法 1+6 2+5 3+4 4+3 5+2 6+1。

输入：n = 30, k = 30, target = 500
输出：222616187
解释：返回的结果必须是对 10^9 + 7 取模。

限制

• 1 <= n, k <= 30
• 1 <= target <= 1000

算法

(动态规划) $O(n \cdot k \cdot target)$

1. 设 $dp(i, j)$ 表示掷了前 $i$ 个骰子，得到总和为 $j$ 的方案数。
2. 初始时，$dp(0, 0) = 1$，表示没有掷骰子时，得到 0 的方案数为 1。其余方案数均为 0。
3. 转移时，枚举这一次掷的骰子的点数。然后，转移 $dp(i, p) = dp(i, p) + dp(i - 1, p - j)$，其中 $1 \le j \le k$，且 $j \le p \le target$。
4. 最后答案为 $dp(n, target)$。

时间复杂度

• 总共有 $n \cdot target$ 个状态，每次转移需要 $O(k)$ 的时间，故总时间复杂度为 $O(n \cdot k \cdot target)$。

空间复杂度

• 和状态数量一致，故空间复杂度为 $O(n \cdot target)$。

C++ 代码

class Solution {
public:
    int numRollsToTarget(int n, int k, int target) {
        const int mod = 1000000007;

        vector<vector<int>> dp(n + 1, vector<int>(target + 1, 0));
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= k; j++)
                for (int p = j; p <= target; p++)
                    dp[i][p] = (dp[i][p] + dp[i - 1][p - j]) % mod;

        return dp[n][target];
    }
};