2021-07-27：给定一个数组arr，长度为N，arr中的值只有1，2，3三种。arr[i] == 1，代表汉诺塔问题中，从

package main

import "fmt"

func main() {
    arr := []int{3, 3, 3}
    if true {
        ret := kth(arr)
        fmt.Println("递归：", ret)
    }
    if true {
        ret := kth2(arr)
        fmt.Println("迭代：", ret)
    }
}

func kth(arr []int) int {
    N := len(arr)
    return step(arr, N-1, 1, 3, 2)
}

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

func kth2(arr []int) int {
    if len(arr) == 0 {
        return -1
    }
    from := 1
    mid := 2
    to := 3
    i := len(arr) - 1
    res := 0
    tmp := 0
    for i >= 0 {
        if arr[i] != from && arr[i] != to {
            return -1
        }
        if arr[i] == to {
            res += 1 << i
            tmp = from
            from = mid
        } else {
            tmp = to
            to = mid
        }
        mid = tmp
        i--
    }
    return res
}