足球挑战:奴才的无聊游戏

Question

编辑：，似乎人们对另一个的这个问题很困惑。这两个问题都是关于同样的Foobar挑战。另一个问题要求一种比指数时间或omega(答案)蛮力搜索更好的方法，因为蛮力搜索花费的时间太长了。那里的答案建议使用动态规划，这是一个好主意，比蛮力搜索或回溯快得多，尽管不是最好的。这个问题是由动态编程( dynamic )开始的，它适用于5个测试中的4个测试，但似乎对第5个测试用例(也可能是最大的测试用例)得到了错误的答案。不会花太长时间。它完成了，但得到了错误的答案。另一个问题的答案对这个问题没有帮助，这个问题的答案对这个问题也没有帮助，所以它们不是重复的。它们是关于同一任务的不同方面的。

我正在进行一次Foobar挑战赛，试图确定个人使用三面模具的可能“获胜”滚动组合的数量。模拟用户将滚动t次在一个一维的“游戏板”，即n个空间宽。三边模有三个可能值:左(-1)，留(0)，右(1)。用户从板上的“0”位置开始。如果你在0的时候，你的a -1 (左)，那么游戏是无效的.如果你在最后的平方，唯一有效的滚动是0(停留)。目标是确定用户可以做出的滚动组合的总数量，最终其标记位于最后一个方格上。(请阅读下面的全部挑战说明)。

对于这一挑战，我有一个半功能的解决方案；然而，当我提交它供评审时，它失败了5个测试场景中的一个；问题是，Foobar没有透露确切的方案是失败的，它只是简单地说'Test 5失败了！‘。有谁能看看我的Java代码(下面)，看看我缺少了什么吗？

这是我的代码：

public static int answer(int t, int n) { 
if ((n - t) > 1) {
    return 0;
}
if (n == 2) {
    return t * 1;
}
if (t == n) {
    return n;
}
// Use dynamic programming:
int lst[] = new int[n]; // lst[k] holds the # valid paths to position k using i-1 steps
int lst2[] = new int[n]; // put # valid paths to position k using i steps into lst2[k]
int total = 0;
lst[0] = 1;
lst[1] = 1;
int max = 1;
for (int i = 1; i < t; i++) {
    lst2 = new int[n];
    if (max < (n - 1)) {
        max++;
    }
    for (int j = 0; j < n && j < (max + 1); j++) {
        if (j == 0) {
            lst2[j] = lst[j] + lst[j + 1];
        } else if (j == max) {
            if (j == (n - 1)) {
                total += lst[j - 1];
            } else {
                lst2[j] = lst[j - 1];
            }
        } else {
            lst2[j] = lst[j - 1] + lst[j] + lst[j + 1];
        }
    }
    lst = lst2;
}
return total % 123454321;
}

原始挑战文本

给你拿着。又一场无聊的“无聊”游戏是布尔教授的无聊的奴才们创造的。

这个游戏是一个单人游戏，在水平行的n个正方形的棋盘上玩。仆从在最左边的正方形上放置一个记号，并滚动一个特殊的三边模具。

如果模具滚动一个“左”，则该仆从将令牌移动到当前所在位置左侧的正方形空间。如果左边没有正方形，则游戏无效，然后重新开始。

如果模具滚动一个“停留”，令牌停留在它的地方。

如果模具滚动一个“右”，则仆从将令牌移动到一个正方形，一个空格移动到当前所在位置的右侧。如果右边没有正方形，则游戏无效，您将重新开始。

目的是准确地掷骰子t次，并在最右边的广场上的最后一卷。如果你在t滚动之前降落在最右边的正方形上，那么唯一有效的骰子就是滚动一个“停留”。如果你滚动任何其他东西，游戏是无效的(也就是说，你不能从最右边的正方形向左或向右移动)。

更有趣的是，仆从们有领导板(每对n，t对)，每个仆从提交他刚才玩的游戏:骰子的顺序。如果某些仆从已经提交了完全相同的顺序，他们不能提交一个新的条目，因此在领导板中的条目对应于独特的游戏可玩性。

由于奴才们经常在移动设备上刷新主板，作为渗透的黑客，您有兴趣知道领导板的最大可能大小。

写一个函数答案( t，n)，它给定骰子的数量t和棋盘n中的正方形数，返回唯一游戏模块123454321的可能数量。也就是说，如果总数是S，那么在将S除以123454321后返回余数，余数应该是0到123454320之间的整数(包括在内)。

N和t将是正整数，不超过1000。N至少是2。

提供Python解决方案的语言，编辑solution.py以提供solution.java解决方案，编辑solution.java

测试用例

投入：(int) t=1 (int) n=2输出：(int) 1

投入：(int) t=3 (int) n=2输出：(int) 3

Answer 1

计数在t中呈指数增长。我的猜测是，错误在于你正在溢出整数范围。减少中间结果mod m，或使用java.math.BigInteger。

Answer 2

好的，为了简单起见，是的，int溢出有一个问题。但是，您不需要使用更大的容器(除了BigInteger )。在第二个数组中存储所有需要的是剩余的ex lst2[j] = (lst[j - 1] + lst[j] + lst[j + 1]) % 123454321;。这样做，您的值将永远不会超过123454321，这将很容易适应一个整数。然后，在我使用total %= 123454321;的每次迭代之后，您只需要返回总计。由于我们只是在添加路径，所以对中间结果进行建模，只会将其减少到一个可管理的数目。