DP Explained | C++
\n> Approach\n1. All we need to do is count permutations with restriction\n2. DP is the best option for such type of problems \n3. We need to keep track of idx(
\n> Approach\n1. All we need to do is count permutations with restriction\n2. DP is the best option for such type of problems \n3. We need to keep track of `idx(how many rolls we have done)`, `previous rolled value,  `count of previous rolled value`. \n\n> Algorithm \n\n```\nlong long int dp[5005][7][16];\n    const int mod = 1e9+7;\n    \n\t// utility function\n    void addSelf(long long int &a, long long int b) {\n        a += b;\n        a %= mod;\n    } \n    \n    long long int go(int idx, int n, int prevRolled, int prevRollCnt, vector<int> &rollMax) {\n        // all rolls done, 1 permutation found\n\t\tif(idx == n) {\n            return 1;\n        }\n        \n\t\t// create a alias, since dp[][][] looks bad\n        long long int &ans = dp[idx][prevRolled][prevRollCnt];\n        if(ans != -1) {\n            return ans;\n        }\n        ans = 0;\n        \n\t\t// try rolling every number and find what is possible\n        for(int i=0; i<6; i++) {\n            if(prevRolled == i+1) {\n\t\t\t// the same number is rolled that was rolled previously \n                if(prevRollCnt < rollMax[i]) {\n\t\t\t\t // ok, we can roll one more time \n                    addSelf(ans, go(idx+1, n, prevRolled, prevRollCnt + 1, rollMax));\n                } else {\n\t\t\t\t\t// countinuous count exceeded, cant roll this anymore \n\t\t\t\t}\n\t\t\t\t\n            } else {\n\t\t\t\t// roll a different number from the previous, with count = 1\n                addSelf(ans, go(idx+1, n, i+1, 1, rollMax));\n            }\n        }\n        \n        return ans;\n    }\n    \n    int dieSimulator(int n, vector<int>& rollMax) {\n        memset(dp, -1, sizeof(dp));\n\t\t// initially 0 is rolled with 0 count \n\t\t// so that we have all the possiblilties for the first roll\n        return go(0, n, 0, 0, rollMax);\n    }\n```
[]