題目描述：

LeetCode上的 擲骰子模擬 題目描述通常如下：

題目：擲骰子模擬（Simulation of Dice Rolling）

原題鏈接

描述：

有一個(gè)骰子模擬器，每次投擲時(shí)都會生成一個(gè)1到6的隨機(jī)數(shù)。不過，在使用這個(gè)模擬器時(shí)有一個(gè)約束條件：連續(xù)擲出數(shù)字i的次數(shù)不能超過rollMax[i]（其中i從1開始編號）。

給定一個(gè)整數(shù)數(shù)組rollMax和一個(gè)整數(shù)n，請計(jì)算投擲n次骰子可得到的不同點(diǎn)數(shù)序列的數(shù)量。兩個(gè)序列如果至少存在一個(gè)元素不同，就認(rèn)為這兩個(gè)序列是不同的。由于答案可能很大，所以請返回模10^9 + 7之后的結(jié)果。

示例：

輸入：
n = 2, rollMax = [1, 1, 2, 2, 2, 3]
輸出：
34
解釋：
我們擲2次骰子，如果沒有約束的話，共有6 * 6 = 36種可能的組合。但是根據(jù)rollMax數(shù)組，數(shù)字1和2最多連續(xù)出現(xiàn)一次，所以不會出現(xiàn)序列(1,1)和(2,2)。因此，最終答案是36-2 = 34。

提示：

1 <= n <= 5000
rollMax.length == 6
1 <= rollMax[i] <= 15

請注意，由于答案可能非常大，所以在計(jì)算過程中需要對結(jié)果進(jìn)行取模操作，以避免溢出。在這個(gè)問題中，我們通常使用模10^9 + 7來得到最終的結(jié)果。

題目思路：

1. 暴力搜索：遞歸解法(會超時(shí))

想法：

先用最暴力的想法去思考這個(gè)問題：

首先，擲一個(gè)骰子(設(shè)值為x)會發(fā)生那些情況呢？

既然題目有 rollMax 的限制，那么分類討論：

• 如果和上一個(gè)骰子值相同，那么 x 的連續(xù)出現(xiàn)次數(shù)不能超過 rollMax[x]；
• 如果不同，那么可以重置連續(xù)出現(xiàn)次數(shù)為 1。

使用遞歸的手段，模擬出每一個(gè)情況的狀態(tài)，相當(dāng)于暴力搜索每一種狀態(tài)，然后再遞歸的過程中通過遞歸工作棧記錄狀態(tài)的參數(shù)(因?yàn)槊看芜f歸參數(shù)都會保留在遞歸工作?？臻g)，我們這里記錄的參數(shù)是三個(gè)。

為什么是三個(gè)呢？又是那三個(gè)？

看看前面的分類討論，提取關(guān)鍵詞：「上一個(gè)骰子值」和「連續(xù)出現(xiàn)次數(shù)」

所以遞歸記錄的狀態(tài)參數(shù)分別是：

• 剩余擲骰子的次數(shù)，用 id 表示（注意：為了方便后面轉(zhuǎn)成遞推，定義成剩余(即為從后往前遞歸枚舉));
• 上一個(gè)骰子值，用 last 表示；
• last的剩余連續(xù)出現(xiàn)次數(shù)，用 consistency 表示。

這樣就確定了遞歸的參數(shù)：(int id,int last,int consistency)，而這個(gè)遞歸的參數(shù)也就表示了一種狀態(tài)。

遞歸的返回值就是骰子序列個(gè)數(shù)。

而后就開始了遞歸中的操作，我們在每次遞歸時(shí)只需要枚舉6中狀態(tài)，也就是擲骰子的六種可能性，而對于每次投擲骰子，我們需要考慮兩種可能的情況：

1. 投擲的骰子值和上一次不同：如果我們想投擲一個(gè)與上一次不同的骰子值 i，我們需要確保 i 的連續(xù)投擲次數(shù)不會超過 rollMax[i]。因此，我們可以遞歸調(diào)用 dfs(id-1, i, rollMax[i]-1)，表示我們投擲了 n - id 次骰子，上一次的值是 last，并且還可以連續(xù)投擲 rollMax[i]-1 次相同的骰子 i。

2. 投擲的骰子值和上一次相同：如果上一次投擲的值是 last，并且 consistency（表示連續(xù)相同骰子的次數(shù)）大于0，那么我們可以繼續(xù)投擲相同的骰子，并減少 consistency 的計(jì)數(shù)。遞歸調(diào)用會是 dfs(id-1, i, consistency-1)，意味著我們投擲了 n - id 次骰子，上一次的值是 last，并且還可以連續(xù)投擲 consistency-1 次相同的骰子。

枚舉 j=0,1,2,3,4,5 把遞歸后的結(jié)果相加，就是當(dāng)前 dfs(id,last,consistency) 的答案。

遞歸到 id == 0 時(shí)結(jié)束，返回 1，表示找到了一個(gè)合法骰子序列。

最后，不要忘了在每一步計(jì)算中取模以避免整數(shù)溢出，特別是當(dāng) n 很大時(shí)。模數(shù)通常是 10^9 + 7，如題目所要求。

代碼

$時(shí)間復(fù)雜度：O(6^n)$

class Solution {
public:
    typedef long long ll;
    int N = 5010,mod = 1e9 + 7;
    vector<int> dices;
    int dfs(int id,int last,int consistency) { 
        if (id == 0) return 1;

        ll res = 0;
        for (int i = 0;i < 6;i ++ ) {
            if (i != last) res = (res + dfs(id - 1,i,dices[i] - 1)) % mod;
            else {
                if (consistency) res = (res + dfs(id - 1,i,consistency - 1)) % mod;
                else continue;
            }
        }
        return res % mod;
    }
    int dieSimulator(int n, vector<int>& rollMax) {
        dices = rollMax;
        ll res = 0ll;
        for (int i = 0;i < 6;i ++ ) {
            res = (res + dfs(n - 1,i,dices[i] - 1)) % mod;
        }
        return (int)res;
    }
};

2. 優(yōu)化：記憶化搜索：遞歸解法(不超時(shí))

想法

舉個(gè)例子，「先擲 1后擲 3」和「先擲 2 后擲 3」，都會遞歸到 dfs(n?2,3,rollMax[3]?1),也就是說無論你上一次搖到幾，下一次遞歸的參數(shù)都是不變，也就是遞歸存儲的狀態(tài)是一致的。

一葉知秋，整個(gè)遞歸與回溯過程是有大量重復(fù)遞歸調(diào)用的。由于遞歸函數(shù)沒有副作用，無論多少次調(diào)用 dfs(id,last,consistency) 算出來的結(jié)果都是一樣的，因此可以用 記憶化搜索 來優(yōu)化，利用一個(gè)三維數(shù)組存儲用三個(gè)參數(shù)的遞歸狀態(tài)：

如果一個(gè)狀態(tài)（遞歸入?yún)ⅲ┦堑谝淮斡龅?，那么可以在返回前，把狀態(tài)及其結(jié)果記到一個(gè) dp 數(shù)組（或者哈希表）中；

 int dp[5010][6][15];//存每次遞歸的返回值
 /*
        id:剩余擲骰子的次數(shù), last：上一個(gè)骰子值, consistency：last的剩余連續(xù)出現(xiàn)次數(shù)
        (i)                               (j)                                (k)
        dp[i][j][k]表示 
 */

如果一個(gè)狀態(tài)不是第一次遇到，那么直接返回 dp 中保存的結(jié)果。

以上正是記憶化搜索的解法，實(shí)際上記憶化搜索就是用數(shù)組/哈希表來記錄遞歸的每個(gè)狀態(tài)，遞歸過程中遇到重復(fù)狀態(tài)則提前返回。

代碼

$時(shí)間復(fù)雜度：O(6?{\sum }_{i=0}^{n}rollMax[i]),由于是遞歸執(zhí)行,實(shí)際上還要大一些$

class Solution {
public:
    typedef long long ll;
    int N = 5010,mod = 1e9 + 7;
    vector<int> dices;
    int dp[5010][6][15];//存每次遞歸的返回值
    
    int dfs(int id,int last,int consistency) {
        if (id == 0) return 1;
        int *val = &dp[id][last][consistency];
        if (*val >= 0) return *val;

        ll res = 0;
        for (int i = 0;i < 6;i ++ ) {
            if (i != last) res = (res + dfs(id - 1,i,dices[i] - 1)) % mod;
            else {
                if (consistency) res = (res + dfs(id - 1,i,consistency - 1)) % mod;
                else continue;
            }
        }
        *val = res % mod;
        return res % mod;
    }
    int dieSimulator(int n, vector<int>& rollMax) {
        memset(dp,-1,sizeof(dp));
        dices = rollMax;
        ll res = 0ll;
        for (int i = 0;i < 6;i ++ ) {
            res = (res + dfs(n - 1,i,dices[i] - 1)) % mod;
        }
        return (int)res % mod;
    }
};

3. 二次優(yōu)化：動態(tài)規(guī)劃：遞推解法(不超時(shí))

想法

將上面的記憶化搜索的遞歸解法一比一翻譯成遞推的解法，就是動態(tài)規(guī)劃

我們可以去掉遞歸中的「遞」，只保留「歸」的部分，即自底向上計(jì)算。

做法：

• dfs 改成 dp 數(shù)組；
• 遞歸改成循環(huán)（每個(gè)參數(shù)都對應(yīng)一層循環(huán)）;
• 遞歸邊界改成 dp 數(shù)組的初始值。

就完事了。

代碼

$時(shí)間復(fù)雜度：O(6?{\sum }_{i=0}^{n}rollMax[i]),由于是循環(huán)執(zhí)行,實(shí)際上還要小一些$文章來源地址http://www.zghlxwxcb.cn/news/detail-841564.html

class Solution {
public:
    typedef long long ll;
    int N = 5010,mod = 1e9 + 7;
    int dp[5010][6][15];//存每次遞歸的返回值
    /*
        id:剩余擲骰子的次數(shù), last：上一個(gè)骰子值, consistency：last的剩余連續(xù)出現(xiàn)次數(shù)
        (i)                               (j)                                (k)
        dp[i][j][k]表示 
    */
    int dieSimulator(int n, vector<int>& rollMax) {
        for (int j = 0;j < 6;j ++ ) {
            for (int k = 0;k < rollMax[j];k ++ ) {
                dp[0][j][k] = 1;
            }
        }

        for (int i = 1;i < n;i ++ ) {
            for (int j = 0;j < 6;j ++ ) {
                for (int k = 0;k < rollMax[j];k ++ ) {
                    ll temp_ans = 0;
                    for (int that = 0;that < 6;that ++ ) {
                        if (that != j) temp_ans = (temp_ans + dp[i - 1][that][rollMax[that] - 1]) % mod;
                        else {
                            if (k) temp_ans = (temp_ans + dp[i - 1][that][k - 1]) % mod;
                            else continue;
                        }
                    }
                    dp[i][j][k] = temp_ans % mod;
                }
            }
        }

        ll res = 0;
        for (int j = 0;j < 6;j ++ ) {
            res = (res + dp[n - 1][j][rollMax[j] - 1]) % mod;
        }

        return (int)res % mod;
    }
};

到了這里，關(guān)于擲骰子(從暴力搜索 到 記憶化搜索 到 動態(tài)規(guī)劃)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！