hdoj 1207 汉诺塔II dp 动态规划

题目描述: http://acm.hdu.edu.cn/showproblem.php?pid=1207(中文)

题目分析:
以下思路转自:http://yxq0620.blog.163.com/blog/static/4449439220102245168595/

初看很难,理解了会发现真的很简单的...

不明白的建议看一下 http://poj.org/problem?id=1958这题,里面有dp 的思路.

如果不明白就继续看吧. 

dp[n]表示 将n个盘子通过4根柱子移动到目的柱子的最小的步数, f( i )表示 把 i个盘子通过 3根柱子移动到目的柱子的最小步数,f(i) 题目已经给出.

dp[ n ] =min(dp[ i ] * 2 + f(n - i));

dp[n]可以通过状态转移方程写出来,或许有的人看了状态转移方程,觉得很难想到,或者看不懂这个方程的意思,我来说说我自己的理解...

要将n各盘子移动到目的的柱子, 而要求最小的步数,所以先 将上面的k个盘子 通过4根柱子移动到 不是目的柱子和开始柱子的另外两个柱子的其中一个. 然后, 现在除了开始的柱子以外,剩下空的柱子就只有2根了. 所以就将剩下的 n-k个柱子通过3根柱子来移动到目地柱子, 最后 将开始 上面的k各盘子 通过4根柱子移动到目的柱子上面,

(1<=k<n);

所以状态转移方程就是这个样子

#include <iostream>
using namespace std;

int main() {
    unsigned long long step[65];
    unsigned long long f[65];
    f[1] = 1;
    unsigned long long i,j,min,cur,t = 1;
    for(i = 2; i < 64; i++)  //注意:只处理到i = 63
        f[i] = (t << i) - 1;//f[i] = (int)(pow(2, i) - 1);
    //f[i] = 2 * f[i - 1] + 1;

    step[0] = 0;
    step[1] = 1;
    step[2] = 3;
    for(i = 3; i <= 64; i++) {
        min = 0xffffffffffffffffUUL;  //UUL 表示unsigned long long, 我的g++ 不加UUL能过, 提交的时候却总是CE, 加上UUL, AC, 其实min 大于18433 就行
			
        for(j = 1; j < i; j++) {
            cur = 2 * step[j] + f[i - j];
            if(cur < min)
                min = cur;
        }
        step[i] = min;
    }
    int n;
    while(cin>>n)
        cout<<step[n]<<endl;
    return 0;
}

注意:
1. 只用long long 或是 __int64 计算过程会溢出, 所以要加unsigned
2. 由于用unsigned long long, 编译器要选g++
3. 有大牛发现以下规律, 所以该题不用dp 也能AC
规律：
step[1]=1;
step[2]=step[1]+2; step[3]=step[2]+2;(2个加2^1)
step[4]=a[3]+4; step[5]=step[4]+4; step[6]=step[5]+4;(3个加2^2);
…………………………………………(4个加2^3);
O(∩_∩)O~