【动态规划】POJ_1958 Strange Towers of Hanoi

本文主要是介绍【动态规划】POJ_1958 Strange Towers of Hanoi，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

输出n个盘子在4个塔的汉诺塔问题最少要多少步。

思路

我们设f[n]为n个盘子在4塔的汉诺塔问题下需要的最少步数，d[i]为i个盘子在3塔的汉诺塔问题下需要的最少步数，可以得出动态转移方程：
$f[n]=min(2*f[i]+d[n-i])$
表示我们在4塔模式下把前i个盘移到B塔上，然后在3塔模式下把n-i个盘移到D塔上，再在4塔模式下把之前i个塔移到D塔上。

代码

#include<cstdio>
#include<algorithm>
using namespace std;
int f[13],d[13];
int main()
{for (int i=1;i<=12;i++) d[i]=2*d[i-1]+1;//预处理3塔模式下每个盘的步数for (int n=1;n<=13;n++){f[n]=2*f[1]+d[n-1];//先赋个初值for (int j=2;j<n;j++)f[n]=min(2*f[j]+d[n-j],f[n]);//动态转移方程if (n==1) continue;else printf("%d\n",f[n]);}
}

这篇关于【动态规划】POJ_1958 Strange Towers of Hanoi的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---