[Java-two method] - DP solutions and DFS solution
1. DP solution\ndp[x][i][k] means num of sequences after x-th roll, when the sequence with tail i. and the consective num of tail i is k.\nex: 1,3,2,2,2 -> dp[5
#### 1. DP solution\ndp[x][i][k] means num of sequences after x-th roll, when the sequence with tail i. and the consective num of tail i is k.\nex: 1,3,2,2,2 -> dp[5][2][3] means 5-th roll ending with 2, the num consective 2 is 3.\n\n**state transfer:**\nso go to (x+1)-th roll from x-th roll, put j at the ending of the pre sequence.\n\n```\n\t1. dp[x+1][j][k+1] += dp[x][i][k]    //  if i == j && k+1<= rollMax[j]\n\t2. dp[x+1][j][1] += dp[x][i][k]           // if i != j && rollMax[j] >= 1\n```\nindex of rollMax is from 1.\n\nThanks for @kkzeng advice. improve the dp code. time 30ms\n\nso the code is as below:\n```\nprivate static final int MOD = 1000000007;\npublic int dieSimulator(int n, int[] rollMax) {\n        if (n == 0) return 0;\n        int[][][] dp = new int[n+1][7][16];\n\t\t// initialization\n        for (int i = 1; i <= 6; ++i) {\n            if (rollMax[i-1] > 0) {\n                dp[1][i][1] = 1;\n            }\n        }\n        for (int x = 2; x <= n; ++x) {\n            for (int i = 1; i <= 6; ++i) {\n\t\t\t\t// if continue to add tail i, make sure consective num of i would less than or equal to rollMax[i-1]\n\t\t\t\tfor (int k = 1; k < rollMax[i-1]; ++k) {\n\t\t\t\t\tdp[x][i][k+1] = (dp[x][i][k+1]+dp[x-1][i][k])%MOD;\n\t\t\t\t}\n\t\t\t   // if add new tail j that differs from i, so we should jump out i\n\t\t\t\tfor (int j = 1; j <= 6; ++j) {\n\t\t\t\t\tif (j == i) continue;\n\t\t\t\t\tfor (int k = 1; k <= rollMax[i-1]; ++k) {\n\t\t\t\t\t\tdp[x][j][1] = (dp[x][j][1]+dp[x-1][i][k])%MOD;\n\t\t\t\t\t}\n\t\t\t\t}\n            }\n        }\n        int num = 0;\n        for (int i = 1; i <= 6; ++i) {\n            for (int k = 1; k <= 15; ++k) {\n                num = (num + dp[n][i][k]) % MOD;\n            }\n        }\n        return num;\n    }\n```\n\nof course, you can make the dp array from 3-dim to 2-dim.\n\n</br>\n\n#### 2. DFS+Memorization(37ms)\nSame solution, but i think the top-down dfs is easier to understand.\n```\npublic int dieSimulator(int n, int[] rollMax) {\n\tint[][][] mem = new int[n+1][7][16];\n\treturn cal(n, 0, 0, rollMax, mem);\n}\n// tail is the tail number of sequence, consectiveNum is the consective num of the sequence tail.\nprivate int cal(int leftRolls, int tail, int consectiveNum, int[] rollMax, int[][][] mem) {\n\tif (leftRolls <= 0) return 1;\n\tint ans = 0;\n\tif (mem[leftRolls][tail][consectiveNum] > 0) {\n\t\treturn mem[leftRolls][tail][consectiveNum];\n\t}\n\tfor (int k = 1; k <= 6; ++k) {\n\t\t// new tail\n\t\tif (k != tail && rollMax[k-1] >= 1) {\n\t\t\tans = (ans + cal(leftRolls-1, k, 1, rollMax, mem))%MOD;\n\t\t}\n\t\t// same tail\n\t\tif (k == tail && rollMax[k-1] >= consectiveNum+1) {\n\t\t\tans = (ans + cal(leftRolls-1, k, consectiveNum+1, rollMax, mem))%MOD;\n\t\t}\n\t}\n\tmem[leftRolls][tail][consectiveNum] = ans;\n\treturn ans;\n}\n```\n
['Dynamic Programming']