leetcode题解-1155-掷骰子的N种方法

发表于 | 更新于 | 分类于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int numRollsToTarget(int d, int f, int target) 
    {
        if (d < 1 || f < 1 || target < 1 || target > d*f)
        {
            return 0;
        }

        // 1.
        int MOD = 1000000007;
        // 2.
        int MIN = min(f, target);
        // 3.
        int MAX = d*f;

        vector<vector<int>> dp(d+1, vector<int>(MAX+1, 0));

        for (int j = 1; j <= MIN; ++j)
        {
            dp[1][j] = 1;
        }

        for (int i = 2; i <= d; ++i)
        {
            // 因为每个筛子至少丢出来的值是 >=1 的
            for (int j = i; j <= MAX; ++j)
            {
                for (int k = 1; j - k >= 0 && k <= f; ++k)
                {
                    dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % MOD;
                }
            }
        }


        return dp[d][target];
    }

};