P1223 - Dice Roll Simulation, Leetcode

Problem Description

给定一个骰子, 需要摇 n 次; 给定一个数组rollMax[i], 1 <= i <= 6, 表示数字 i 最多可以连续出现rollMax[i]次. 求不同的序列数. 返回的值模 1e9+7.

Analysis

考虑 2 个骰子

Code

java

class Solution {
    private static final long MOD = (long) 1e9 + 7;
    private int[] rollMax;

    public int dieSimulator(int n, int[] rollMax) {
        this.rollMax = rollMax;
        int m = rollMax.length;
        long ans = 0;
        for (int j = 0; j < m; ++j)
            ans += dfs(n - 1, j, rollMax[j] - 1);
        return (int) (ans % MOD);
    }

    private int dfs(int i, int last, int left) {
        if (i == 0) return 1;
        long res = 0;
        for (int j = 0; j < rollMax.length; ++j)
            if (j != last) res += dfs(i - 1, j, rollMax[j] - 1);
            else if (left > 0) res += dfs(i - 1, j, left - 1);
        return (int) (res % MOD);
    }
}