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

这篇具有很好参考价值的文章主要介绍了掷骰子(从暴力搜索 到 记忆化搜索 到 动态规划)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述:

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 <= n <= 5000
rollMax.length == 6
1 <= rollMax[i] <= 15

请注意,由于答案可能非常大,所以在计算过程中需要对结果进行取模操作,以避免溢出。在这个问题中,我们通常使用模10^9 + 7来得到最终的结果。

题目思路:

1. 暴力搜索:递归解法(会超时)

想法:

先用最暴力的想法去思考这个问题:

首先,掷一个骰子(设值为x)会发生那些情况呢?

既然题目有 rollMax 的限制,那么分类讨论:

  • 如果和上一个骰子值相同,那么 x 的连续出现次数不能超过 rollMax[x]
  • 如果不同,那么可以重置连续出现次数为 1

使用递归的手段,模拟出每一个情况的状态,相当于暴力搜索每一种状态,然后再递归的过程中通过递归工作栈记录状态的参数(因为每次递归参数都会保留在递归工作栈空间),我们这里记录的参数是三个。

为什么是三个呢?又是那三个?

看看前面的分类讨论,提取关键词:「上一个骰子值」和「连续出现次数」

所以递归记录的状态参数分别是:

  • 剩余掷骰子的次数,用 id 表示(注意:为了方便后面转成递推,定义成剩余(即为从后往前递归枚举));
  • 上一个骰子值,用 last 表示;
  • last的剩余连续出现次数,用 consistency 表示。

这样就确定了递归的参数:(int id,int last,int consistency),而这个递归的参数也就表示了一种状态。

递归的返回值就是骰子序列个数。

而后就开始了递归中的操作,我们在每次递归时只需要枚举6中状态,也就是掷骰子的六种可能性,而对于每次投掷骰子,我们需要考虑两种可能的情况:

  1. 投掷的骰子值和上一次不同:如果我们想投掷一个与上一次不同的骰子值 i,我们需要确保 i 的连续投掷次数不会超过 rollMax[i]。因此,我们可以递归调用 dfs(id-1, i, rollMax[i]-1),表示我们投掷了 n - id 次骰子,上一次的值是 last,并且还可以连续投掷 rollMax[i]-1 次相同的骰子 i

  2. 投掷的骰子值和上一次相同:如果上一次投掷的值是 last,并且 consistency(表示连续相同骰子的次数)大于0,那么我们可以继续投掷相同的骰子,并减少 consistency 的计数。递归调用会是 dfs(id-1, i, consistency-1),意味着我们投掷了 n - id 次骰子,上一次的值是 last,并且还可以连续投掷 consistency-1 次相同的骰子。

枚举 j=0,1,2,3,4,5 把递归后的结果相加,就是当前 dfs(id,last,consistency) 的答案。

递归到 id == 0 时结束,返回 1,表示找到了一个合法骰子序列。

最后,不要忘了在每一步计算中取模以避免整数溢出,特别是当 n 很大时。模数通常是 10^9 + 7,如题目所要求。

代码

时间复杂度: O ( 6 n ) 时间复杂度:O(6^n) 时间复杂度:O(6n)

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. 优化:记忆化搜索:递归解法(不超时)

想法

举个例子,「先掷 1后掷 3」和「先掷 2 后掷 3」,都会递归到 dfs(n−2,3,rollMax[3]−1),也就是说无论你上一次摇到几,下一次递归的参数都是不变,也就是递归存储的状态是一致的。

一叶知秋,整个递归与回溯过程是有大量重复递归调用的。由于递归函数没有副作用,无论多少次调用 dfs(id,last,consistency) 算出来的结果都是一样的,因此可以用 记忆化搜索 来优化,利用一个三维数组存储用三个参数的递归状态:

如果一个状态(递归入参)是第一次遇到,那么可以在返回前,把状态及其结果记到一个 dp 数组(或者哈希表)中;

 int dp[5010][6][15];//存每次递归的返回值
 /*
        id:剩余掷骰子的次数, last:上一个骰子值, consistency:last的剩余连续出现次数
        (i)                               (j)                                (k)
        dp[i][j][k]表示 
 */

如果一个状态不是第一次遇到,那么直接返回 dp 中保存的结果。

以上正是记忆化搜索的解法,实际上记忆化搜索就是用数组/哈希表来记录递归的每个状态,递归过程中遇到重复状态则提前返回。

代码

时间复杂度: O ( 6 ∗ ∑ i = 0 n r o l l M a x [ i ] ) , 由于是递归执行 , 实际上还要大一些 时间复杂度:O(6*\sum_{i=0}^{n} rollMax[i]),由于是递归执行,实际上还要大一些 时间复杂度:O(6i=0nrollMax[i]),由于是递归执行,实际上还要大一些

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. 二次优化:动态规划:递推解法(不超时)

想法

将上面的记忆化搜索的递归解法一比一翻译成递推的解法,就是动态规划

我们可以去掉递归中的「递」,只保留「归」的部分,即自底向上计算。

做法:

  • dfs 改成 dp 数组;
  • 递归改成循环(每个参数都对应一层循环);
  • 递归边界改成 dp 数组的初始值。

就完事了。

代码

时间复杂度: O ( 6 ∗ ∑ i = 0 n r o l l M a x [ i ] ) , 由于是循环执行 , 实际上还要小一些 时间复杂度:O(6*\sum_{i=0}^{n} rollMax[i]),由于是循环执行,实际上还要小一些 时间复杂度:O(6i=0nrollMax[i]),由于是循环执行,实际上还要小一些文章来源地址https://www.toymoban.com/news/detail-841564.html

class Solution {
public:
    typedef long long ll;
    int N = 5010,mod = 1e9 + 7;
    int dp[5010][6][15];//存每次递归的返回值
    /*
        id:剩余掷骰子的次数, last:上一个骰子值, consistency:last的剩余连续出现次数
        (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;
    }
};

到了这里,关于掷骰子(从暴力搜索 到 记忆化搜索 到 动态规划)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包