汉诺塔

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
现在蒜头君开始玩汉诺塔游戏， 他放了 n 片黄金圆盘在第一根柱子上，从上到下依次编号为 1-n,1号圆盘最小，n号圆盘最大号。蒜头君移动第
i号圆盘的时候需要花费 i 点体力。现在蒜头君想把圆盘全部移动到底 2根柱子上，移动过程中蒜头君必须准守游戏规则。

现在蒜头君想知道他完成游戏的最小移动次数和最少消耗的体力。

输入格式

输入一个正整数 n(1≤n≤60) 表示黄金圆盘的个数

输出格式

一行输出 2 个数，表示最小移动次数和最小消耗的体力，中间用一个空格隔开。

样例输入1

2
样例输出1

3 4
样例输入2

3
样例输出2

7 11

解题思路：

一共就三步

1. 把 n-1 号盘子移动到缓冲区
2. 把1号从起点移到终点
3. 然后把缓冲区的n-1号盘子也移到终点

我们令f(n)为把n个盘子移动到目的地执行的次数。

1. 第一步即f(n-1)
2. 第二步即1
3. 第三步即f(n-1)

注意：当n=1时，代表除目的地外只剩下一只盘子，这时，只需移动一次就可以了。

我们令f(x)为把n个盘子移动到目的地消耗的体力
1.第一步即f(n-1)

1. 第二步即1乘n，因为把第n个盘子移动到目的地即消耗1*n个体力
2. 第三步即f(n-1)

注意：当n=1时，代表除目的地外只剩下一只盘子，且最后那个盘子一定是编号1，即消耗1体力的那个，因此只需要消耗一个体力即可。

这样我们写出了递归，但是有缺陷，就是f(n-1)重复执行了两次，为了避免多余的消耗，我们利用动态规划记录过程，减少了不必要的浪费，其实2*f(n-1)就可以~~~，但是难以理解。

#include<iostream>
#define ll long long
using namespace std;
// int fun1(int n){
//     if(n==1)    return 1;
//     else    return fun1(n-1)+n+fun1(n-1);

// }
// int fun2(int n){
//     if(n==1)    return 1;
//     else    return fun2(n-1)+1+fun2(n-1);

// }
ll dp[61];
int main(){
    int n;
    cin>>n;
    dp[1]=1;
    for(int i=2;i<=n;++i){
        dp[i]=2*dp[i-1]+1;
    }
    cout<<dp[n]<<" ";
    for(int i=2;i<=n;++i){
        dp[i]=2*dp[i-1]+i;
    }
    cout<<dp[n];
}