Detailed thoughts from brute force (DFS) to recursion with memorization
Since the problem is a "all solution" problem, using brute force can always solve the problem. All fancy algorithms like greedy, dynamic programming are all opt
Since the problem is a "all solution" problem, using brute force can always solve the problem. All fancy algorithms like greedy, dynamic programming are all optimizations of brute force solution. Therefore, If there is no idea for a optimized solution, starting from a brute force will do no harm. Here I use depth-first search to exclusively search for every possible solution. The idea is as follows: \n\nfor each level, we maintain a last variable to record down the last dice we rolled. \nat each level, we did not consider the same number we rolled as the last number.\n\ninstead, we keep trying the same number for up to rollMax[i] times for each possible number at a given roll. \n\ntherefore, there are at most n levels of recursion here, and at each level we first go through each possible value form 1 to 6, and for each value, we iterate through rollMax[i - 1] times. Let\'s say Max(rollMax[i]) is M, \nTime complexity: O((6M)^n)\nspace complexity O(n)\n\n```\nclass Solution {\n    private int count = 0;\n    public int dieSimulator(int n, int[] rollMax) {\n        dfs(n, rollMax, -1);\n        return count;\n    }\n    \n    private void dfs(int n, int[] rollMax, int last) {\n        if (n == 0) {\n            count++;\n            return;\n        }\n        for (int i = 1; i <= 6; i++) {\n            if (i == last) {\n                continue;\n            }\n            for (int j = 1; j <= rollMax[i - 1] && n - j >= 0; j++) {\n                dfs(n - j, rollMax, i);\n            }\n        }\n    }\n}\n```\n\nHowever, if we want to apply memorization, we must transfer the code into pure recursion (there are no side effects on each level). We can defines the subproblem as:\nrecursion(n, last) represent the number of different outcome for n times. We modify the code as follows:\n\n```\nprivate int recursion(int n, int[] rollMax, int last) {\n        if (n == 0) {\n            return 1;\n        } \n        int result = 0;\n        for (int i = 1; i <= 6; i++) {\n            if (i == last) {\n                continue;\n            }\n            for (int j = 1; j <= rollMax[i - 1] && n - j >= 0; j++) {\n                result += recursion(n - j, rollMax, i);\n                result = result %= 1000000007;\n            }\n        }\n        return result;\n    }\n\n\t\n```\nfinally, we apply memorization:\n```\n\n\tclass Solution {\n    private int count = 0;\n    public int dieSimulator(int n, int[] rollMax) {\n        int[][] dp = new int[n + 1][7];\n        return dfs(n, rollMax, 0, dp);\n    }\n    \n    private int dfs(int n, int[] rollMax, int last, int[][] dp) {\n        if (n == 0) {\n            return 1;\n        } else if (dp[n][last] > 0) {\n            return dp[n][last];\n        }\n        int result = 0;\n        for (int i = 1; i <= 6; i++) {\n            if (i == last) {\n                continue;\n            }\n            for (int j = 1; j <= rollMax[i - 1] && n - j >= 0; j++) {\n                result += dfs(n - j, rollMax, i, dp);\n            }\n        }\n        dp[n][last] = result;\n        return result;\n    }\n}\n\n```\nTime complexity: O(6n)\nSpace: O(6n)\n\t\n\t
[]