Java recursive to DFS with cache with explaination
\nJava basic recursive solution\n\npublic int dieSimulator(int n, int[] max) {\n        int result = 0;\n        return dfs(n, max, 0, 0);\n    }\n\n    private
```\nJava basic recursive solution\n\npublic int dieSimulator(int n, int[] max) {\n        int result = 0;\n        return dfs(n, max, 0, 0);\n    }\n\n    private int dfs(int n, int[] max, int last, int count ){\n        if(n == 0)\n            return 1;\n        int result = 0;\n        for(int i = 1; i < 7; i ++){\n            if(i == last && max[last-1] == count){\n                continue;\n            }\n            if(last == i)\n                result += dfs(n-1, max, last, count+1);\n            else\n                result += dfs(n-1, max, i, 1);\n        }\n        return result;\n    }\n\t\nIf we observe closely, there are three variables for each recursive call:-\n1. the remaining dice rolls\n2. the last rolled value\n3. the count of the consecutive rolls of the last value.\nHence, we can use a cache here to store the result of each state :-\n\nLong[][][] dp;\n    int MOD = 1000000007;\n    public int dieSimulator(int n, int[] max) {\n        dp = new Long[5001][7][16];\n        return (int)(dfs(n, max, 0, 0)%MOD);\n    }\n\n    private long dfs(int n, int[] max, int last, int count ){\n        if(n == 0)\n            return 1;\n        long result = 0;\n        if(dp[n][last][count] != null)\n            return dp[n][last][count];\n        for(int i = 1; i < 7; i ++){\n            if(i == last && max[last-1] == count){\n                continue;\n            }\n            if(last == i)\n                result = (result + dfs(n-1, max, last, count+1)) % MOD;\n            else\n                result = (result + dfs(n-1, max, i, 1))%MOD;\n        }\n        dp[n][last][count] = result;\n        return result% MOD;\n    }\n```
[]