网址:https://www.acwing.com/problem/content/98/
题意:
求$4$个塔的$$Hanoi$塔问题的最小移动步数。
题解:
三个塔时,我们知道将$n$个盘移动到一个塔的最小次数是$2^{n}-1$,令其为$d[n]$,对于$n+1$个盘,则为$(2×d[n])+1$(先移$n$个组成一个塔然后移底座,再把它们归位),所以对于$4$个塔时,我们先把$i$个盘子移动到一个塔,剩下的$n-i$个盘子转化成三个塔的问题,枚举$i$求最小值即可。
实际上,推广到$m$个塔$n$个盘的情况时,由$Frame-Stewart$算法,有最小次数:
(参考博客:https://blog.csdn.net/pijk55556/article/details/100527696)
AC代码:
#include <bits/stdc++.h> using namespace std; long long dp[15], f[15]; int main() { dp[1] = 1; for (int i = 2; i <= 12; ++i) dp[i] = (dp[i - 1] << 1) + 1; f[1] = 1; for (int i = 2; i <= 12; ++i) { f[i] = (f[1] << 1) + dp[i - 1]; for (int j = 2; j < i; ++j) f[i] = min(f[i], (f[j] << 1) + dp[i - j]); } for (int i = 1; i <= 12; ++i) printf("%lld\n", f[i]); return 0; }