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

Question

假设您有一个长度为n的垂直游戏板(即空格数).而且你有一个三面骰子可以选择:前进一个,留下并返回一个.如果你低于或高于棋盘游戏空间的数量,这是一个无效的游戏.一旦你到达董事会的最后,唯一有效的举措是"留下来".鉴于精确的掷骰数量t,是否可以通过算法计算出能够赢得比赛的独特骰子数量？

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

例如:t = 1,n = 2; 输出= 1 t = 3,n = 2; 输出= 3

Answer 1

您可以使用动态编程方法.复发的草图是:

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

奖金:花哨的"单线"与列表compreehension和减少

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]