立方体行走方案数 - 动态规划解法

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

令 '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)'，可以通过本题。