c++ - 骰子分布的直方图

Question

我在 careercup 上看到一个问题，但我没有在那里得到我想要的答案。我自己写了一个答案，希望您对我对时间复杂度的分析以及对算法和代码的评论发表评论。或者您可以在时间方面提供更好的算法。谢谢。

给你 d > 0 个公平的骰子，其中 n > 0 个“面”，编写一个函数返回掷骰结果频率的直方图。

例如，对于 2 个骰子，每个骰子有 3 个面，结果是:

(1, 1) -> 2
(1, 2) -> 3
(1, 3) -> 4
(2, 1) -> 3
(2, 2) -> 4
(2, 3) -> 5
(3, 1) -> 4
(3, 2) -> 5
(3, 3) -> 6

函数应该返回:

2: 1
3: 2
4: 3
5: 2
6: 1

(我的溶胶)。如果使用强力深度优先搜索，时间复杂度为 O(n^d)。但是，可以使用DP思想来解决这个问题。例如，d=3 和 n=3。在计算 d==2 时可以使用 d==1 的结果:

d==1

num  #
1    1
2    1
3    1

d==2

first roll     second roll is 1
num  #         num  # 
1    1         2    1                  
2    1      -> 3    1
3    1         4    1

first roll     second roll is 2
num  #         num  # 
1    1         3    1                  
2    1      -> 4    1
3    1         5    1

first roll     second roll is 3
num  #         num  # 
1    1         4    1                  
2    1      -> 5    1
3    1         6    1

因此，

second roll
num  #
2    1
3    2
4    3
5    2
6    1

这个DP算法的时间复杂度是

SUM_i(1:d) {n*[n(d-1)-(d-1)+1]} ~ O(n^2*d^2)
               ~~~~~~~~~~~~~~~ <--eg. d=2, n=3, range from 2~6 

用C++写的代码如下

vector<pair<int,long long>> diceHisto(int numSide, int numDice) {
int n = numSide*numDice;
vector<long long> cur(n+1,0), nxt(n+1,0);
for(int i=1; i<=numSide; i++) cur[i]=1;

for(int i=2; i<=numDice; i++) { 
    int start = i-1, end = (i-1)*numSide; // range of previous sum of rolls
    //cout<<"start="<<start<<"   end="<<end<<endl;
    for(int j=1; j<=numSide; j++) {
        for(int k=start; k<=end; k++) 
            nxt[k+j] += cur[k];
    }

    swap(cur,nxt);
    for(int j=start; j<=end; j++) nxt[j]=0; 
}
vector<pair<int,long long>> result;
for(int i=numDice; i<=numSide*numDice; i++)
    result.push_back({i,cur[i]});
return result;

Answer 1

您可以在 O(n*d^2) 中完成。首先，注意 n 面骰子的生成函数是 p(n) = x+x^2+x^3+...+x^n，并且 d 次掷出的分布具有生成函数 p(n )^d。将多项式表示为数组，您需要 O(nd) 个系数，并且通过保持滚动总和可以在 O(nd) 时间内在单次通过中完成乘以 p(n)。

这是一些实现它的 python 代码。它有一个不明显的优化:它从每个 p(n) 中抛出一个因子 x(或者等效地，它将骰子视为具有面 0,1,2,...,n-1 而不是 1,2， 3,...,n) 这就是为什么在显示分布时将 d 添加回来的原因。

def dice(n, d):
    r = [1] + [0] * (n-1) * d
    nr = [0] * len(r)
    for k in xrange(d):
        t = 0
        for i in xrange(len(r)):
            t += r[i]
            if i >= n:
                t -= r[i-n]
            nr[i] = t
        r, nr = nr, r
    return r

def show_dist(n, d):
    for i, k in enumerate(dice(n, d)):
        if k: print i + d, k

show_dist(6, 3)

时间和空间复杂度很容易看出:有 d 和 (n-1)*d 次迭代的嵌套循环，所以时间复杂度为 O(n.d^2)，并且有两个大小为 O(nd) 和没有其他分配，所以空间复杂度为O(nd)。