奇怪的汉诺塔

https://www.acwing.com/problem/content/98/

思路：

定义dp3[i]与dp4[i]分别为三根柱与四根柱的汉诺塔问题的 i 个盘子的解

1. 先将 j 个盘子移到 B 或 C 柱，这是四个柱的汉诺塔问题，移动步数为dp4[j]
2. 将剩余 i - j 个盘子移动到 D 柱，这是三个柱的汉诺塔问题，移动步数为dp3[i - j]
3. 再将第一步 j 个盘子移动到 D 柱，移动步数为dp4[j]

状态转移方程：dp4[i] = min(dp4[i], dp4[j] * 2 + dp3[i - j])

ac代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 15;

int n;
int dp3[N], dp4[N];

int main(){
    n = 12;
    for(int i = 1; i <= n; i ++) dp3[i] = (1 << i) - 1;
    memset(dp4, 0x3f, sizeof dp4);
    dp4[0] = 0;
    for(int i = 1; i <= n; i ++){
        for(int j = 0; j < i; j ++){
            dp4[i] = min(dp4[i], dp4[j] * 2 + dp3[i - j]);
        }
    }
    for(int i = 1; i <= n; i ++) cout << dp4[i] << '\n';
    return 0;
}