Strange Towers of Hanoi(递归/递推/dp)

发布于 2020-06-25  0 次阅读


题目大意:

求出n盘四柱Hanoi的最优解
原题面参考:牛客网

思路:

三柱Hanoi问题中,递推公式为的d[n]=2d[n-1]+1; 原因: 1、将n-1个盘放在B柱(利用C柱)上需要d[n-1]步 2、将最后一个放在C上需要一步 3、将B柱上的n-1个移到C上(利用A)需要d[n-1]步 共需要2d[n-1]+1步,其中d[1]=1;
四柱Hanoi问题中,递推公式为f[n]=min(f[n],f[i]*2+d[n-i]);
原因:
1、将i个盘放在B上需要f[i]步,剩下A、C、D即可变成三柱Hanoi问题
2、将A上剩下的盘子移到D需要d[n-i]步(三柱递推公式得)
3、将B柱上的盘移到D需要f[i]步
共需要2f[i]+d[n-i]步,其中f[1]=1;
此题为求最优解,所以应该枚举放在B柱上的盘的可能性,求得最小的步数f[n]

AC Code:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int f[15], d[15];
int main()
{
	memset(f, INF, sizeof(f));
	f[1] = 1, d[1] = 1;
	for (int i = 2; i <= 12; i++)   //三柱Hanoi
		d[i] = d[i - 1] * 2 + 1;
	for (int i = 1; i <= 12; i++)
	{
		for (int j = 1; j < i; j++)    //求得最小的步数
			f[i] = min(f[i], f[j] * 2 + d[i - j]);  
		cout << f[i] << endl;
	}
	return 0;
}

平平无奇的在校大学生