给定与总和匹配的长度的 3 位数字 (-1,0,1) 的唯一序列数

Question

假设您有一个长度为 n（即空格数）的垂直游戏板。你有一个三面骰子，它有以下选项：前进一枚，留下一枚，后退一枚。如果您低于或高于棋盘游戏空间的数量，则该游戏无效。到达棋盘末端后，唯一有效的移动是 "stay"。给定准确的掷骰数 t，是否可以通过算法计算出导致游戏获胜的唯一掷骰数？

到目前为止，我已经尝试为给定的掷骰数生成一个 (-1,0,1) 的所有可能组合的列表，并对列表进行排序以查看是否有任何加起来达到板并满足成为有效游戏的所有要求。但这对于 20 以上的骰子掷骰是不切实际的。

例如： t=1，n=2；输出=1 t=3，n=2；输出=3

Answer 1

尝试回溯算法。递归地 "dive down" 进入深度 t 并且只继续可能仍然导致有效状态的骰子值。可能通过传递一个 "remaining budget" 来实现。

例如，n=10, t=20，当您达到 20 的深度 10 并且您的预算仍然是 10（= 向前和向后的步骤似乎被取消）时，下一个递归步骤直到深度 t 将停止 0 和 -1 的可能性，因为它们最终无法产生有效状态。

这种情况下的回溯算法仍然很重（指数级），但比先用所有可能性吹泡泡然后过滤要好。

Answer 2

您可以使用动态规划方法。一个循环的草图是：

M(0, 1) = 1
M(t, n) = T(t-1, n-1) + T(t-1, n) + T(t-1, n+1)

当然你必须考虑边界情况（比如离开棋盘或不允许退出棋盘的末端，但很容易编写代码）。

这是一些 Python 代码：

def solve(N, T):
    M, M2 = [0]*N, [0]*N

    M[0] = 1
    for i in xrange(T):
        M, M2 = M2, M
        for j in xrange(N):
            M[j] = (j>0 and M2[j-1]) + M2[j] + (j+1<N-1 and M2[j+1])

    return M[N-1]

print solve(3, 2) #1
print solve(2, 1) #1
print solve(2, 3) #3
print solve(5, 20) #19535230

奖励：花式 "one-liner" 具有列表理解和减少

def solve(N, T):
    return reduce(
        lambda M, _: [(j>0 and M[j-1]) + M[j] + (j<N-2 and M[j+1]) for j in xrange(N)], 
        xrange(T), [1]+[0]*N)[-1]

Answer 3

设 M[i, j] 为 N by N 矩阵，如果 |i-j| <= 1 则为 M[i, j] = 1，否则为 0（特殊情况为M[N, N-1] = 0)

的 "stay" 规则

此矩阵计算从位置 i 到位置 j 的长度 1 的路径。

要找到长度为 t 的路径，只需提高 M 的 t 次方即可。这可以通过线性代数包有效地执行。

解可以读出：M^t[1, N].

例如，在交互式 Python 会话中，在大小为 5 的棋盘上计算长度为 20 的路径：

>>> import numpy
>>> M = numpy.matrix('1 1 0 0 0;1 1 1 0 0; 0 1 1 1 0; 0 0 1 1 1; 0 0 0 0 1')
>>> M
matrix([[1, 1, 0, 0, 0],
        [1, 1, 1, 0, 0],
        [0, 1, 1, 1, 0],
        [0, 0, 1, 1, 1],
        [0, 0, 0, 0, 1]])
>>> M ** 20
matrix([[31628466, 51170460, 51163695, 31617520, 19535230],
        [51170460, 82792161, 82787980, 51163695, 31617520],
        [51163695, 82787980, 82792161, 51170460, 31628465],
        [31617520, 51163695, 51170460, 31628466, 19552940],
        [       0,        0,        0,        0,        1]])

所以在大小为 5 的板上有 M^20[1, 5]，即 19535230 条从头到尾长度为 20 的路径。

Answer 4

由于可以在任何地方添加零，我们将这些可能性乘以 (-1) 的不同排列：

X (space 1) X (space 2) X (space 3) X (space 4) X

(-1) 只能出现在 spaces 1,2 或 3 中，不能出现在 space 4 中。我用计算在不向后跳过的情况下放置减号的方法的数量。

JavaScript代码：

function C(n,k){if(k==0||n==k)return 1;var p=n;for(var i=2;i<=k;i++)p*=(n+1-i)/i;return p}

function sumCoefficients(arr,cs){
  var s = 0, i = -1;
  while (arr[++i]){
    s += cs[i] * arr[i];
  }
  return s;
}

function f(n,t){
  var numMinusOnes = (t - (n-1)) >> 1
      result = C(t,n-1),
      numPlaces = n - 2,
      cs = [];

  for (var i=1; numPlaces-i>=i-1; i++){
    cs.push(-Math.pow(-1,i) * C(numPlaces + 1 - i,i));
  }

  var As = new Array(cs.length),
      An;

  As[0] = 1;

  for (var m=1; m<=numMinusOnes; m++){
    var zeros = t - (n-1) - 2*m;
    An = sumCoefficients(As,cs);
    As.unshift(An);
    As.pop();
    result += An * C(zeros + 2*m + n-1,zeros);
  }
  return result;
}

输出：

console.log(f(5,20))
19535230

给定与总和匹配的长度的 3 位数字 (-1,0,1) 的唯一序列数

Number of unique sequences of 3 digits (-1,0,1) given a length that matches a sum

algorithm

math

graph-algorithm