AcWing 80. 骰子的点数

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 80. 骰子的点数原题链接简单

作者：

cornerCao , 2019-01-24 20:44:16 , 所有人可见 , 阅读 5578

19

11

算法1

(动归) $O(n^2)$

考虑用动归，数组dp[i][j]表示用i个骰子扔出和为j的可能数，因为第i个骰子可能扔出1-6的点数，则dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+dp[i-1][j-4]+dp[i-1][j-5]+dp[i-1][j-6]，由于我们只需要用到最后一次的结果，因此为了节省空间可以使用滚动数组，将二维dp数组变为一维。

时间复杂度分析：$O(n^2)$

C++ 代码

class Solution {
public:
    vector<int> numberOfDice(int n) {
        vector<int>dp(6*n+1, 0);
        for(int i = 1;i<=6;i++)//动归数组初始值，表示1个骰子扔出1-6的可能数都为1
            dp[i] = 1;
        for(int i = 2;i<=n;i++){
            for(int j = 6*i;j>=0;j--){
                dp[j] = 0;
                for(int k = 6;k>=1;k--){//最后一个骰子可以扔1-6点
                    if(j-k<0)
                        continue;
                    dp[j] += dp[j-k];
                }
            }
        }
        vector<int>res(dp.begin()+n, dp.end());//扔n个骰子的和为[n, 6*n]
        return res;
    }
};

9 评论

KillLemon 2021-01-17 12:26

未优化的版本

class Solution {
public:
    vector<int> numberOfDice(int n) {
        vector<int> res;
        int dp[n + 1][6 * n + 1];   //这里后面的大小是6 * n + 1，因为是数值的大小
        memset(dp,0,sizeof dp);
        for(int i = 1; i <= 6; i ++) dp[1][i] = 1;
        for(int i = 2;i <= n; i ++)
            for(int j = i;j <= 6 * i; j ++)
                for(int k = 1; k <= 6; k ++)
                    if(j - k > 0)
                        dp[i][j] += dp[i - 1][j - k];
        for(int i = n; i <= 6 * n; i ++) res.push_back(dp[n][i]);
        return res;
    }
};

Syse 2021-03-28 17:43

为啥j要从i开始？

WuLiYa 2022-01-11 11:28 回复了 Syse 的评论

因为j表示投掷i次的总和，我投掷i次筛子，总和最低是从i*1开始的吧，所以j是从i开始的
举个例子
当i=2时，表示我投掷了两次，总和（j）最小从2开始的，就是我两次投掷的都为1，不可能说j从1开始遍历，而是从i开始遍历。

马里奥 2020-06-27 22:44

请问j为啥是到0不是到2

希望 2020-12-15 10:59

比如算到第3轮，并且求到dp[3]（实际上是二维状态下的dp[3][3]），它应该等于dp[2][1]+dp[2][2]。而dp[2][1]不是一个合法状态，值应该为0，所以题解中的代码实际上起到了将不合法状态置0的作用。
如果代码中j递减到的是i，还是上面的例子，只会更新到dp[2][2]，没有清空dp[2][1]，这样的话接下去计算dp[3][3]就出错了。