c++ simple O(n) dp with explanation
C++\nclass Solution {\nprivate:\n    const int mod = 1e9 + 7;\npublic:\n    int dieSimulator(int n, vector<int>& rollMax) {\n        vector<vector<long long>> d
```C++\nclass Solution {\nprivate:\n    const int mod = 1e9 + 7;\npublic:\n    int dieSimulator(int n, vector<int>& rollMax) {\n        vector<vector<long long>> dp(n + 1, vector<long long>(7));\n        for (int i = 0; i < 6; i++) \n            dp[0][i] = 0, dp[1][i] = 1;\n        dp[0][6] = 1, dp[1][6] = 6;\n        for (int i = 2; i <= n; i++) {\n            long long sum = 0;\n            for (int j = 0; j < 6; j++) {\n                dp[i][j] = dp[i - 1][6];\n                if (i - rollMax[j] - 1 >= 0)\n                    dp[i][j] = (dp[i][j] - (dp[i - rollMax[j]- 1][6] - dp[i - rollMax[j] - 1][j]) + mod) % mod;\n                sum = (sum + dp[i][j]) % mod;\n            }\n            dp[i][6] = sum % mod;\n        }\n        return dp[n][6];\n    }\n};\n```\n\ndp[i][j] means how many cases there is when roll i times ends with j;\nif there is no restriction, `dp[i][j] = sum(dp[i-1])` ( 0 < i < 6)\nand we need to minus those unsatisfied , which starts with j at roll `i - rollMax[j]` and then all j, but which before that cannot be j, so it should `sum[i - rollMax[j] - 1] - dp[i - rollMax[j] - 1][j]`
[]