给定的长度为3位（-1,0,1）的独特序列的数目相匹配的总和 [英] Number of unique sequences of 3 digits (-1,0,1) given a length that matches a sum

问题描述

假设你有一个长度为n的垂直游戏板（是的空格数）。而你有一个有选择的三面骰子：向前走的，留回去之一。如果你去以下或以上的棋盘游戏空格数这是一个无效的比赛。唯一有效的举措，一旦你到达板到底是留。鉴于模辊牛逼一个确切的数字，是否有可能通过算法计算出独特的掷骰的那个导致比赛获胜多少？

Say you have a vertical game board of length n (being the number of spaces). And you have a three-sided die that has the options: go forward one, stay and go back one. If you go below or above the number of board game spaces it is an invalid game. The only valid move once you reach the end of the board is "stay". Given an exact number of die rolls t, is it possible to algorithmically work out the number of unique dice rolls that result in a winning game?

到目前为止，我已经试过生产的（-1,0,1）每个可能的组合的名单模辊的给定数量，并通过列表排序，以查看是否有任何加起来板的长度和也满足了作为一个有效的游戏需求。但是，这是不切实际的掷骰高于20。

So far I've tried producing a list of every possible combination of (-1,0,1) for the given number of die rolls and sorting through the list to see if any add up to the length of the board and also meet all the requirements for being a valid game. But this is impractical for dice rolls above 20.

例如： 吨= 1，n = 2时;输出= 1 吨= 3中，n = 2;输出= 3

For example: t=1, n=2; Output=1 t=3, n=2; Output=3

推荐答案

您可以使用动态规划方法。复发的素描是：

You can use a dynamic programming approach. The sketch of a recurrence is:

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

当然，你必须要考虑的边界的情况下（就像去了董事会或不允许退出董事会的结束，但它很容易code表示）。

Of course you have to consider the border cases (like going off the board or not allowing to exit the end of the board, but it's easy to code that).

下面是一些Python code：

Here's some Python code:

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

奖励：看中一班轮与名单COM preehension并减少

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]

这篇关于给定的长度为3位（-1,0,1）的独特序列的数目相匹配的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！