C++|Die Simulator with 3D DP Explained| Recursive | Memoize |
\n# Complexity\n- Time complexity: O(n * 6 * 6 * 16)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(n * 6 * 16)\n\n# Code\ncpp []\nclass S
\n# Complexity\n- Time complexity: O(n * 6 * 6 * 16)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n * 6 * 16)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    // Helper function to count the number of valid sequences\n    int helper(int n, int i, int cnt, vector<int>& rollMax, vector<vector<vector<int>>>& dp) {\n        // Base case: if there are no more rolls left, we\'ve found a valid sequence\n        if (n == 0) {\n            return 1;\n        }\n\n        // Check if this state (n, i, cnt) has already been computed\n        if (dp[n][i][cnt] != -1) {\n            return dp[n][i][cnt];\n        }\n\n        int ans = 0;\n\n        // Try rolling all 6 faces of the die (from 0 to 5)\n        for (int k = 0; k < 6; k++) {\n            // If we are rolling the same face again and we have reached the max count for this face, skip\n            if (i == k && cnt >= rollMax[k]) {\n                continue;\n            }\n            // If it\'s the same face, increase the consecutive count\n            if (i == k) {\n                ans += helper(n - 1, i, cnt + 1, rollMax, dp);\n            } \n            // If it\'s a different face, reset the consecutive count to 1\n            else {\n                ans += helper(n - 1, k, 1, rollMax, dp);\n            }\n            // Since the answer can be very large, take the result modulo 1000000007\n            ans %= 1000000007;\n        }\n\n        // Save the computed result for this state\n        return dp[n][i][cnt] = ans;\n    }\n\n    // Main function to calculate the number of distinct sequences\n    int dieSimulator(int n, vector<int>& rollMax) {\n        // DP table initialized with -1 (meaning the state is not yet computed)\n        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(6, vector<int>(16, -1)));\n        int ans = 0;\n\n        // Try starting with each face of the die (from 0 to 5)\n        for (int i = 0; i < 6; i++) {\n            ans += helper(n - 1, i, 1, rollMax, dp);\n            ans %= 1000000007;  // Take modulo at each step\n        }\n\n        return ans;\n    }\n};\n\n\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']