k柱漢諾塔

題目描述

漢諾塔（Hanoi Tower），又稱河內塔。
傳說大梵天創造世界的時候做了三根金剛石柱子，按左、中、右排序。大梵天在左側的柱子上，從下往上按照大小順序摞著64片黃金圓盤，越靠下的圓盤越大。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放到右側的柱子上。并且規定，任何時候，較小的圓盤都不能被較大的圓盤壓著，且一個步驟只能移動一個圓盤。
小明復刻了這個故事為一套游戲道具，但他發現以他有生之年是移不完這些圓盤的——實際上，原始的故事下，需要 2^64-1 = 18446744073709551615（約 1.8 * 10^19）個步驟才能移動完畢。
基于此，他將柱子的數量改為k個，再將圓盤的數量改為n個。
請你幫助小明計算，修改后的游戲需要多少個步驟能操作完畢。

關于輸入

輸入為兩個正整數k和n，以空格隔開，分別代表修改后的游戲有k根柱子和n個圓盤。
提供三個輸入樣例。

關于輸出

輸出為一個正整數s，代表需要的最少步驟數。
提供三個輸出樣例。

例子輸入

4 5

例子輸出

13

解題分析

代碼實現

#include <stdio.h>
#include <math.h>
#define MAX 100int dict[MAX][MAX] = {0};int help(int n, int m) {if (n < 0 || m < 3) {return -1;}if (n == 1) {return 1;}if (dict[n][m] != 0) {return dict[n][m];}int nowValue;if (m == 3) {nowValue = pow(2, n) - 1;} else {nowValue = 2 * help(n - 1, m) + help(1, m - 1);for (int i = n - 2; i > 0; i--) {int temp = 2 * help(i, m) + help(n - i, m - 1);if (temp < nowValue) {nowValue = temp;} else {break;}}}dict[n][m] = nowValue;return nowValue;
}int main() {int n, m;scanf("%d", &n); scanf("%d", &m);printf("%d",help(m,n));return 0;
}