1223. 掷骰子模拟

题目链接：1223. 掷骰子模拟

方法：回溯 + 记忆化搜索

解题思路

1. 回溯要点

• 参数列表
  根据题目中的操作确定在递归中需要用到的上一层的某个变量或性质。
• 递归边界
  即递归的最底层，确定其返回值。

2. 记忆化搜索
   由于在递归中会重复计算某一状态的值，那么我们在第一次计算出来后将其保存在数组中，再下一次遇到该状态时直接取出数值即可。

代码

class Solution {
private:
    const long long MOD = 1e9 + 7;
public:
    int dieSimulator(int n, vector<int>& rollMax) {
        int m = rollMax.size(), cache[n][m][15];
        memset(cache, -1, sizeof(cache));
        function<int(int, int, int)> dfs = [&](int i, int last, int left) -> int {
            if (i == 0) return 1;
            if (cache[i][last][left] != -1) return cache[i][last][left];
            long long res = 0;
            for (int j = 0; j < m; j ++ ) {
                if (j != last) res += dfs(i - 1, j, rollMax[j] - 1);
                else if (left) res += dfs(i - 1, last, left - 1);
            }
            cache[i][last][left] = res % MOD;
            return res % MOD;
        };
        long long ans = 0;
        for (int j = 0; j < m; j ++ ) {
            ans += dfs(n - 1, j, rollMax[j] - 1) % MOD;
        }
        return ans % MOD;
    }
};

复杂度分析

时间复杂度：\(O(nmS)，S = \sum rollMax\)；
空间复杂度：\(O(nS)\)。