Strange-Towers-of-Hanoi

title: Strange Towers of Hanoi
date: 2023-12-11 03:20:05
tags: 递推
categories: 算法进阶指南

题目大意

解出 $n$ 个盒子 $4$ 座塔的汉诺塔问题最少需要多少次？

思路

首先考虑 $n$ 个盒子 $3$ 座塔的经典汉诺塔问题，设 $d[n]$ 表示求解该 $n$ 题的最少步数，即把 $n-1$ 个盒子从 $A$ 柱移动到 $B$ 柱，然后把第 $n$ 个盒子从 $A$ 柱移动到 $C$ 柱，然后把前 $n-1$ 个盒子从 $B$ 柱移动到 $C$ 柱子。四塔模式下，转化为三塔模式，先移动 $i$ 个，移动到 $B$ 柱子，将 $n-i$ 个盒子移动到 $D$ 柱子，然后再把 $i$ 个盒子从 $B$ 柱移动到 $D$ 柱子。就是将四塔转化为三塔，运用三塔的思维来进行解题

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 22;


int d[N],f[N];//三层和四层汉诺塔
//三层汉诺塔 d[n] = 2 * d[n - 1] + 1;
//四层汉诺塔，转化为三层汉诺塔问题
int main()
{
   
    memset(f,0x3f,sizeof f);
	d[1] = f[1] = 1;
    for(int i = 2;i <= 12; i ++){
   
        d[i] = 2 * d[i - 1] + 1;
    }
    cout << 1 << endl;
    for(int i = 2; i <= 12; i ++){
   
        for(int j = 1; j <= i; j ++){
   
            f[i] = min(f[i],2 * f[j]  + d[i - j]);
        }
        cout << f[i] << endl;
    }
	return 0;
}