你现在正站在一个立方体上如下图所示你初始时站在0号顶点上你每次移动只能沿着边往相邻的顶点移动一步不能不走现在问n步之后你回到 0号顶点的方案数

我们可以使用动态规划来解决这个问题。

令 $f[i][j]$ 表示走了 $i$ 步，当前在 $j$ 号顶点的方案数。则最终答案为 $f[n][0]$。

考虑如何转移。假设当前在 $j$ 号顶点，可以转移到相邻的 $k$ 号顶点，那么 $f[i][j]$ 可以由 $f[i-1][k]$ 转移而来。因此，状态转移方程为：

$$f[i][j] = \sum_{k=0}^7 f[i-1][k], \text{if } j \text{ 与 } k \text{ 相邻}$$

边界条件为 $f[0][0] = 1$，其余的 $f[0][j] = 0$。

最终的时间复杂度为 $O(n)$，可以通过本题。