C++/Java two-dimensional DP with explanation
DP[i][j] means the total number of combinations at round i we get a j at current round, considering the constraint.\n\nExplanation\nLet J be any integer in 1 to
`DP[i][j]` means the total number of combinations at round `i` we get a `j` at current round, considering the constraint.\n\n**Explanation**\nLet `J` be any integer in 1 to 6, and the maximum roll amount be `k`, then at round `i` we only allow:\n`J^CJ`,\n`J^CJJ`,\n`...`,\n`J^CJJ...J`, (`k` consecutive `J`)\nwhere `J^C` represents a number that is not `J`, namely the complementary set of `J`.\n\n**DP approach**\nIt is not difficult to see that `DP[i][j] = DP[i-k][j^C] + ... + DP[i-1][j^C].` Upon noticing that `DP[i][j^c] = sum[i] - DP[i][j]`, where `sum[i]` represents total number of combinations at round `i` considering the constraint, we end up with a two-dimensional DP, and an additional one-dimensional DP to quickly obtain `sum[i]`.\n\nThe code should be pretty self-explanatory.\n\n**C++**\n```\nclass Solution {\npublic:\n    int dieSimulator(int n, vector<int>& rollMax) {\n        long p = 1e9 + 7;\n        vector<vector<long>> dp(n+1, vector<long>(6, 0));\n        vector<long> sum(n+1, 0);\n        sum[0] = 1;\n        for (int i = 1; i <= n; ++i) {\n            for (int j = 0; j < 6; ++j)  {\n                for (int k = 1; k <= rollMax[j] && i - k >= 0; ++k)\n                    dp[i][j] = (dp[i][j] + sum[i-k] - dp[i-k][j] + p) % p;\n                sum[i] = (sum[i] + dp[i][j]) % p;\n            }                \n        }\n        \n        return sum[n];\n    }\n};\n```\nTime: `O(6n max(rollMax))` = `O(n max(rollMax))`,\nSpace: `O(6n) + O(n)` = `O(n)`.\n\n\n**Java**\n```\nclass Solution {\n    public int dieSimulator(int n, int[] rollMax) {\n        long p = 1_000_000_007;\n        long[][] dp = new long[n + 1][6];\n        long[] sum = new long[n+1];\n        sum[0] = 1;\n        for (int i = 1; i <= n; ++i) {\n            for (int j = 0; j < 6; ++j)  {\n                for (int k = 1; k <= rollMax[j] && i - k >= 0; ++k)\n                    dp[i][j] = (dp[i][j] + sum[i-k] - dp[i-k][j] + p) % p;\n                sum[i] = (sum[i] + dp[i][j]) % p;\n            }                \n        }\n        \n        return (int) sum[n];\n    }\n}\n```
['Dynamic Programming', 'C', 'Java']