讨论/题目交流/🏆 第 158 场力扣周赛/
🏆 第 158 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

分割平衡字符串
可以攻击国王的皇后
掷骰子模拟
最大相等频率

展开讨论
力扣 (LeetCode)发起于 2019-10-13
最近编辑于 2019-10-14

我反而觉得第三题比较好想,就是计数dp的变形一下,开三维数组
dp[i][j][k]:代表的是 (现在选第i个数,现在选的数字是j,当前这个数字已经选了k次)
这个状态转移就很明显了:
dp[i][j][1] += dp[i-1][k][t] (t < rowMax(k) && j != k),也就是我这次选择的数字为j,上一个数字为k,不管上一次k已经选了多少个t,我现在也是新选的j。
dp[i][j][t] += dp[i-1][j][t-1] ( 1 < t <= rowMax(j)),也就是我上一次选择的数字为j,这次还选数字为j,遍历的时候不超过约束即可。然后统计dp[n][][]的所有情况。

public class test22 {


    private final long mod = 1000000007;
    long[][][] dp;

    public void out(int x , int y, int z,long v)
    {
        System.out.println("("+ x +"," + y + "," + z + ") --" + v);
    }

    public int dieSimulator(int n, int[] rollMax) {

        if(n == 0) return 0;

        int max = 0;
        for(int i = 0;i < 6;i++) max = Math.max(max,rollMax[i]);

        dp = new long[n + 1][6 + 1][max + 1];

        for(int i = 0;i <= n;i++)
        {
            for(int j = 0; j <= 6;j++)
            {
                for(int k = 0;k <= max; k++)
                {
                    dp[i][j][k] = 0;
                }
            }
        }

        for(int i = 1;i <= 6;i++) dp[1][i][1] = 1;

        // 当前第几个序列
        for(int i = 2;i <= n; i++)
        {
            // 当前第几个编号
            for(int j = 1; j <= 6;j++)
            {
                // 枚举上一个的编号
                for(int k = 1; k <= 6;k++)
                {
                    if(k != j)
                    {
                        for(int t = 1;t <= rollMax[k - 1];t++)
                        {
                            dp[i][j][1] = (dp[i][j][1] + dp[i-1][k][t]) % mod;
                        }
                    }
                    else
                    {
                        for(int t = 2;t <= rollMax[k - 1];t++)
                        {
                            dp[i][j][t] = (dp[i][j][t] + dp[i-1][k][t - 1]) % mod;
                        }
                    }
                }
            }
        }

        long ans = 0;
        for(int i = 1;i <= 6;i++)
        {
            for(int j = 1;j <= rollMax[i - 1];j++)
            {
                ans = (ans + dp[n][i][j]) % mod;
            }
        }

        return (int)ans;
    }

    public static void main(String[] args) {

        test22 of = new test22();
        int[] rollMax = {1,1,1,2,2,3};
        int n = 3;
        System.out.println(of.dieSimulator(n,rollMax));
    }
}

展开全部 14 讨论