C++ DFS with Memorization
Intuition\n Describe your first thoughts on how to solve this problem. \nUse DFS to simulate all the possibilities.\nUse Memorization to reduce redundant comput
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUse DFS to simulate all the possibilities.\nUse Memorization to reduce redundant computations.\nAt each round, the DFS arguments should include:\n1. round index\n2. prev value \n3. num of consecutive for this value\n\nThe Memorization states should be \n```\nmemo[num_rounds+1][dice_value_each_round+1][consecutive_num_of_this_value+1]\n```\nIn this case, the maximum memory it should occupy is: memo[5001][7][16]\n\n# Code\n```\nclass Solution {\npublic:\n    int dieSimulator(int n, vector<int>& rollMax) {\n\n       auto memo = vector<vector<vector<int>>>(n+1, vector<vector<int>>(7, vector<int>(16, -1))); \n       return DFS(0, n, 0, 0, rollMax, memo);    \n\n    }\n\n    int DFS(int round_index, int n, int consecutive_num, int prev_value, vector<int>& rollMax, vector<vector<vector<int>>>& memo){\n        // base case \n        if(round_index == n){\n            return 1;\n        }\n        // if this branch has been cacluated, directly return\n        if(memo[round_index][prev_value][consecutive_num] != -1)\n            return memo[round_index][prev_value][consecutive_num];\n\n        long long res = 0;\n\n        for(int i=1; i <=6; i++){\n           if(i == prev_value && consecutive_num == rollMax[i-1]){\n               // the consecutive num of this value has exceeded the rollMax, we need to dice the other number\n               continue;\n           }\n           if(i == prev_value){\n                // if current round dice the same number as prev value\n               res += DFS(round_index + 1, n, consecutive_num + 1, prev_value, rollMax, memo) % mod_;\n           }\n           else{\n               res += DFS(round_index + 1, n, 1, i, rollMax, memo) % mod_;\n           }     \n        }\n\n        // update memo\n        memo[round_index][prev_value][consecutive_num] = res % mod_;\n\n        return res % mod_;\n\n    }\n\nprivate:\n    long long mod_ = 1e9 + 7;\n\n};\n\n\n\n// memo[5001][7][16]\n```
['C++']