DP is Easy | C++ easiest solution | beginner level
WARNING: This will not be a tabulated, perfectly optimized DP solution. We have enough of those.\n\nInspiration: (Optional) Go through this to get idea of appro
**WARNING**: This will not be a tabulated, perfectly optimized DP solution. We have enough of those.\n\n**Inspiration**: (Optional) Go through this to get idea of approach [Target Sum discussion](https://leetcode.com/problems/target-sum/discuss/455024/DP-IS-EASY!-5-Steps-to-Think-Through-DP-Questions)\n\n1. **Recursive Approach** (currn is current value of n)\n```\ntypedef long ll;\nll m = 1e9+7;\n\nclass Solution {\npublic:\n    ll help(int n, vector<int>& maxroll, int currn, int prevRoll, int count){\n\t\t//base cases\n        if(currn > n) return 0;\n        \n        if(prevRoll > 0 && maxroll[prevRoll-1] < count) return 0;\n        \n        if(currn == n) return 1;\n\n        ll ans = 0;\n        for(int i = 0 ; i < 6; i++){\n\t\t\t//if prev roll is same increase count else count will be 1 in else part\n            if(prevRoll == i+1) \n                ans = (ans + help(n, maxroll, currn+1, i+1, count+1)) % m;\n            else\n                ans = (ans + help(n, maxroll, currn+1, i+1, 1)) % m;\n        }\n        \n        return ans;\n    }\n    \n    int dieSimulator(int n, vector<int>& rollMax) {\n        ll ans = help(n, rollMax, 0, 0, 0);\n        return ans;\n    }\n};\n```\n\n2. **Memoize the above code. (Just add cache)**\nObserve that in help function 3 parameters are changing while making recursive calls (can you name these?). These should be our cache dimensions.\n```\ntypedef long ll;\nll m = 1e9+7;\n\nclass Solution {\npublic:\n    \n    ll dp[5001][7][16];\n    \n    ll help(int n, vector<int>& maxroll, int currn, int prevRoll, int count){\n\t\t//base cases\n        if(currn > n) return 0;\n        \n        if(prevRoll > 0 && maxroll[prevRoll-1] < count) return 0;\n        \n        if(currn == n) return 1;\n        \n        if(dp[currn][prevRoll][count] != -1) return dp[currn][prevRoll][count];\n        \n        ll ans = 0;\n        for(int i = 0 ; i < 6; i++){\n            if(prevRoll == i+1) \n                ans = (ans + help(n, maxroll, currn+1, i+1, count+1)) % m;\n            else\n                ans = (ans + help(n, maxroll, currn+1, i+1, 1)) % m;\n        }\n        \n        return dp[currn][prevRoll][count] = ans;\n    }\n    \n    int dieSimulator(int n, vector<int>& rollMax) {\n        \n        for(int i = 0 ; i < 5001; i++){\n            for(int j = 0 ; j < 7; j++){\n                for(int k = 0; k < 16; k++){\n                    dp[i][j][k] = -1;\n                }\n            }\n        }\n      \n        ll ans = help(n, rollMax, 0, 0, 0);\n        return ans;\n    }\n};\n```\n\nPlease stop posting 4-5 lines of tabulated solutions **without explanations**.\nThanks
[]