前言

给定一个数组arr，长度为N，arr中的值只有1，2，3三种
arr[i] == 1，代表汉诺塔问题中，从上往下第i个圆盘目前在左
arr[i] == 2，代表汉诺塔问题中，从上往下第i个圆盘目前在中
arr[i] == 3，代表汉诺塔问题中，从上往下第i个圆盘目前在右
那么arr整体就代表汉诺塔游戏过程中的一个状况
如果这个状况不是汉诺塔最优解运动过程中的状况，返回-1
如果这个状况是汉诺塔最优解运动过程中的状况，返回它是第几个状况

解题思路

7层汉诺塔问题的一个状态

最优解的第一个状态
全部盘子都在左边

第二个状态就是1号盘子在右边
第三个状态就是2号盘子在中间

i: 1~i的圆盘需要移动
F: 1~i的圆盘现在处在什么圆盘上，可能是左中右.
t:需要去的位置可能是左，中,右
other:除了from, to的另外一个位置

i层的圆盘没有任何道理是在other.上

如果index还在From上,说明第一大步没走完
第一步:1~i-1 从from到other
第二步:i从from到to
第三步:1~i-1从other到to

把每一步都用递归分解
最后相加,得出为第几步

代码

    public static int kth(int[] arr) {
        int N = arr.length;
        return step(arr, N - 1, 1, 3, 2);
    }

    // 0...index这些圆盘，arr[0..index] index+1层塔
    // 在哪？from 去哪？to 另一个是啥？other
    // arr[0..index]这些状态，是index+1层汉诺塔问题的，最优解第几步
    public static int step(int[] arr, int index, int from, int to, int other) {
        if (index == -1) {
            return 0;
        }
        if (arr[index] == other) {
            return -1;
        }
        // arr[index] == from arr[index] == to;
        if (arr[index] == from) {
            return step(arr, index - 1, from, other, to);
        } else {
            int p1 = (1 << index) - 1;
            int p2 = 1;
            int p3 = step(arr, index - 1, other, to, from);
            if (p3 == -1) {
                return -1;
            }
            return p1 + p2 + p3;
        }
    }