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

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

到目前为止，我已经尝试为给定数量的骰子生成每个可能的 (-1,0,1) 组合的列表，并对列表进行排序，看看是否有任何组合达到了板的长度，并且还满足所有要求成为有效游戏的要求。但对于掷骰子点数超过 20 的情况来说，这是不切实际的。

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

您可以使用动态规划方法。递归的示意图是：

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

奖励：带有列表理解和归约的花式“一行”

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]