HDOJ 1207 汉诺塔II

HDACM1207

采用动态规划的方法来做。
假设上面的a个盘子是通过4根柱子全移到第2个柱子上，则下面(n-a)个盘子只能通过3根柱子移到最后一根柱子上，
此时，h2[n] = h2[a]*2+(long)Math.pow(2,n-a)-1。
显然这不一定是最优解，所以a++依次求直到找到h2[n]的最优解

import java.util.Scanner;public class Main {public static void main(String[] args) {long h2[] = new long[65];h2[1] = 1;h2[2] = 3;h2[3] = 5;for (int i = 4; i < h2.length; i++) {h2[i] = h2[i/2]*2+(long)Math.pow(2, i-i/2)-1;for (int j = i/2+1; j < i; j++) {long t = h2[j]*2+(long)Math.pow(2, i-j)-1;if (t<h2[i]) {h2[i] = t;}}}Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int n = sc.nextInt();System.out.println(h2[n]);}sc.close();}
}