网址: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;
}
01-07 13:26