题目链接

算法竞赛进阶指南-9.奇怪的汉诺塔

Method : DP + 递推

首先要明白，每多一个塔，搬运次数必定减少：比如n个盘，n个塔，只需要$2(n - 1) + 1$次。

因此，关键在于怎么把4塔问题转化为3塔问题:

4塔: A B C D

先把i个盘子放到B塔，然后关注剩下n - i个盘子放到A C D塔，怎么放搬运次数最少=>这样转为3塔问题。

${f[i] = min (f[i], f[j] * 2 + d[i - j])}$

#include <iostream>
#include <cstring>

using namespace std;

const int N = 12 + 7;

int d[N];  // 三塔
int f[N];  // 四塔

int main() {
    
    d[1] = 1;
    for (int i = 2; i <= 12; i ++) {
        d[i] = d[i -1] * 2 + 1;
    }
    
    memset(f, 0x3f, sizeof f);
    f[1] = 1;
    for (int i = 2; i <= 12; i ++) {
        for (int j = 0; j < i; j ++) {
            f[i] = min(f[i], f[j] * 2 + d[i - j]); //依赖3塔min
        }
    }
     
    for (int i = 1; i <= 12; i ++) {
        printf("%d\n", f[i]);
    }
    
    return 0;
}`

复杂度分析

• 时间复杂度${O(n^2)}$， 其中$n^2$为$n$的DP双重循环。

• 空间复杂度${O(n)}$。

PS

推广到5塔，首先是要求出4塔的最小搬运次数，然后再转化为3塔。依次类推求n塔。

5塔问题转化为4塔问题，4塔问题转化为3塔问题…

#include <iostream>
#include <cstring>

using namespace std;

const int N = 12 + 7;

int d[N];  // 三塔
int f[N];  // 四塔
int g[N];  // 五塔

int main() {
    
    d[1] = 1;
    for (int i = 2; i <= 12; i ++) {
        d[i] = d[i -1] * 2 + 1;
    }
    
    memset(f, 0x3f, sizeof f);
    f[1] = 1;
    for (int i = 2; i <= 12; i ++) {
        for (int j = 0; j < i; j ++) {
            f[i] = min(f[i], f[j] * 2 + d[i - j]); //依赖3塔min
        }
    }
    
    memset(g, 0x3f, sizeof g);
    g[1] = 1;    
    for (int i = 2; i <= 12; i ++) {
        for (int j = 0; j < i; j ++) {
            g[i] = min(g[i], g[j] * 2 + f[i - j]); //依赖4塔min
        }
    }
    
    for (int i = 1; i <= 12; i ++) {
        printf("%d\n", e[i]);
    }
    
    return 0;
}