题解 | #汉诺塔问题# [P1-H]

自知表达能力不行肯定讲不清楚，干脆找了个讲的清楚的视频链接
https://www.youtube.com/watch?v=rf6uf3jNjbo

这里我直接recursion了 没去记忆了。
时间O(n^2), 每次recursion会分两支新的recursion
空间O(n), 递归n层，所以栈最高也是n层。

想要动态规划+记忆就把F(n, x, y)存个HashMap<String, LinkedList>
key = String.formart("%d-%d-%d", n, x, y)
value就是solve(n,x,y)的return值。

import java.util.*;

public class Solution {
    public ArrayList<String> getSolution(int n) {
      // Let x, y denote 2 sticks
      // and u(x,y) denotes the other stick that's not x or y.
      // and assign left, mid, right to numbers: 0, 1, 2, 
      // so u(x, y) = 3 - x - y.
      
      // Let F(n, x, y) denotes optimal moves required to move n
      // plates from  x to y.
      // F(n, x, y) = F(n-1, x, u(x,y)) + move(x, y) + F(n-1, u(x,y), y)
      return new ArrayList<String>(solve(n, 0, 2));
    }
  
    LinkedList<String> solve(int n, int x, int y) {
      LinkedList<String> ret;
      // base, move 1 plate from x to y
      if (n == 1) {
        ret = new LinkedList<>();
        ret.addLast(move(x,y));
        return ret;
      }
      // 先 move n-1 plates from x to u(x,y). 
      ret = solve(n-1, x, 3-x-y);
      // 再 move bottom plate from x to y
      ret.addLast(move(x, y));
      // 最后 move n-1 plates from u(x,y) to y
      ret.addAll(solve(n-1, 3-x-y, y));
      
      return ret;
    } 
  
    String move(int x, int y) {
      return String.format("move from %s to %s", idxToStr(x), idxToStr(y));
    }
  
    String idxToStr(int idx) {
      if (idx == 0) return "left";
      if (idx == 1) return "mid";
      return "right";
    }
}