[Java] 2d DP with rolls and the last number
Intuition\nFrom a general case to a special case. Think of how to calculate permutations / combinations.\nPrepare\nConsider how to calculate the whole combinati
**Intuition**\nFrom a general case to a special case. Think of how to calculate permutations / combinations.\n**Prepare**\nConsider how to calculate the whole combinations in `n` rolls (no contraints). Obviously, the answer is `6 ^ n` since each time when we roll, there are always `6` candidates. Let\'s translate this to dynamic programming language. Let `dp[n][i]` be the count of combinations ended by `i` after `n` rolls. \n- `dp[1][i]` is `1`. if we roll once, one chance for each number.\n- `dp[n][i] = sum(dp[n-1][k])` for `k` ranges from `0` to `5` (assume that numbers of dice is zero-based). \n- From above, `dp[n][i] == dp[n][j]` for all `i`, `j` in `[0, 5]`. So `dp[n][i] = 6 * dp[n-1][i]` and we definately will get `dp[n][i]` is `6 ^ (n - 1)`. Finally we sum up `dp[n][i]`, then we get `6 * 6 ^ (n - 1) = 6 ^ n`.\n\nHere is the code. `dieSimulator(n)` will definately return `6 ^ n`.\n```\nclass Solution {\n    public int dieSimulator(int n) {\n        int[][] dp = new int[n][6];\n        // init, roll once, only one sequence end up by every number\n        for (int i = 0; i < 6; i++) dp[0][i] = 1;\n        // start dp\n        for (int i = 1; i < n; i++) {\n            for (int j = 0; j < 6; j++) {\n                dp[i][j] = Arrays.stream(dp[i-1]).sum();\n            }\n        }\n        return Arrays.stream(dp[n-1]).sum();\n    }\n}\n```\n**Algorithm**\nNow something changes. When it come to `dp[n][i]`, we should take care of the consecutive sequence of number `i`:\n1. if `k != i`, `dp[n-1][k]` can still simply transfer to `dp[n][i]`.\n2. if `k == i`, only some of `dp[n-1][k]` can transfer to `dp[n][i]`. For example, `i = 1` and `rollMax[i] = 4`: all the `(n - 1)`-length sequences like `a, ..., x, 1, 1, 1, 1` can not transfer to `dp[n][1]`. We can calculate and exclude these sequences. But, how many sequences like this? Consider `rollMax[i] = 4` and we already have a `(n - 1)`-length sequence. Now we wants to calculate `dp[n][1]`:\n\t```text\n\tn \u2264 4   - - -             nothing needs to be excluded since the previous sequence is shorter than rollMax[1] (4)\n\tn = 5   1 1 1 1           only one needs to be excluded\n\tn = 6   x 1 1 1 1         x could be 0, 2, 3, 4, 5, so dp[0][0] + dp[0][2] + dp[0][3] + dp[0][4] + dp[0][5] need to be excluded.\n\tn = 7   y x 1 1 1 1       x could be 0, 2, 3, 4, 5, so dp[1][0] + dp[1][2] + dp[1][3] + dp[1][4] + dp[1][5] need to be excluded.\n\t...\n\t```\n3. Don\'t forget the modulo: \n`(a + b) % M = (a % M + b % M) % M`\n`(a - b) % M = (a % M - b % M) % M` and in Java modulo could be negtive so you need to bring into an extra `M`, thus `(a % M - b % M + M) % M`\n4. Demensions are either zero-based or one-based makes no difference. In algorithm decribed above, first demension is **one-based**. But in my implementation, they are both zero-based.\n\n**Complexity**\nTime: `O(n)`. Inner loop needs to sum up `dp`s from `0` to `5` but still constant.\nSpac: `O(n)`.\n```\nclass Solution {\n    \n    private static int MOD = 1000000007;\n    \n    public int dieSimulator(int n, int[] rollMax) {\n        int[][] dp = new int[n][6];\n        // init, roll once, only one sequence end up by every number\n        for (int i = 0; i < 6; i++) dp[0][i] = 1;\n        // start dp\n        for (int i = 1; i < n; i++) {\n            for (int j = 0; j < 6; j++) {\n                dp[i][j] = Arrays.stream(dp[i-1]).reduce(0, (a, b) -> (a + b) % MOD);\n                // see 2. in algorithm part\n                if (i == rollMax[j]) dp[i][j]--;\n                else if (i > rollMax[j]) {\n                    for (int k = 0; k < 6; k++) {\n                        if (j != k) dp[i][j] = (dp[i][j] - dp[i - rollMax[j] - 1][k] + MOD) % MOD;\n                    }\n                }\n            }\n        }\n        return Arrays.stream(dp[n-1]).reduce(0, (a, b) -> (a + b) % MOD);\n    }\n}\n```
['Dynamic Programming', 'Java']