掷骰子(从暴力搜索 到 记忆化搜索 到 动态规划)

题目描述：

LeetCode上的 掷骰子模拟 题目描述通常如下：

题目：掷骰子模拟（Simulation of Dice Rolling）

原题链接

描述：

有一个骰子模拟器，每次投掷时都会生成一个1到6的随机数。不过，在使用这个模拟器时有一个约束条件：连续掷出数字i的次数不能超过rollMax[i]（其中i从1开始编号）。

给定一个整数数组rollMax和一个整数n，请计算投掷n次骰子可得到的不同点数序列的数量。两个序列如果至少存在一个元素不同，就认为这两个序列是不同的。由于答案可能很大，所以请返回模10^9 + 7之后的结果。

示例：

输入：

n = 2, rollMax = [1, 1, 2, 2, 2, 3]

输出：

34

解释：

我们掷2次骰子，如果没有约束的话，共有6 * 6 = 36种可能的组合。但是根据rollMax数组，数字1和2最多连续出现一次，所以不会出现序列(1,1)和(2,2)。因此，最终答案是36-2 = 34。

提示：

1