题解 | #循环汉诺塔#

A(abc)

C B

如上图，以n等于3为例，a、b、c表示依次增大的金片。若想将abc移到B，则需要先将c移动到B(c最大挪完就不用管了，所以优先处理)，那么需要ab不压着c且不占用·B，即ab需要从A移动到C才行，然后c再从A移动到B，接着ab再从C移动到B。

可以得到关系式 f(n):1 = f(n - 1):2 + 1 + f(n - 1):2 = 2 * f(n - 1):2 + 1

(其中 f(n):1 表示n层的汉诺塔移动1单位所需的步数， f(n):2 表示n层的汉诺塔移动2单位所需的步数。

同理，f(n):2 = f(n - 1):2 + 1 + f(n - 1):1 + 1 + f(n - 1):2 = 2 * f(n - 1):2 + f(n - 1):1 + 2

而边界值 f(1):1 = 1，f(1):2 = 2，所以可以写出如下代码。

#include <iostream>
#include <vector>

int main()
{
    int n;
    std::cin >> n;

    std::vector<unsigned[2]> dp(n);
    dp[0][0] = 1;
    dp[0][1] = 2;
  
    for (int i = 1; i < n; ++i)
    {
        dp[i][0] = (dp[i - 1][1] * 2 + 1) % 1000000007u;
        dp[i][1] = (dp[i - 1][1] * 2 + dp[i - 1][0] + 2) % 1000000007u;
    }
    std::cout << dp[n - 1][0] << ' ' << dp[n - 1][1];
}

优化一下内存占用得到如下代码。

#include <iostream>

int main()
{
    int n;
    std::cin >> n;
  
    unsigned dp0 = 1, dp1 = 2;
    for (int i = 1; i < n; ++i)
    {
        unsigned tmp = (dp1 << 1) + 1;
        dp1 = (tmp + dp0 + 1) % 1000000007u;
        dp0 = tmp % 1000000007u;
    }
    std::cout << dp0 << ' ' << dp1;
}