从递归到树再到动态规划

// 容易堆栈溢出
// 判断 A B 大小减少递归次数
const multiplyRecursionAdd = function (A, B) {
  if (A === 0) {
    return 0;
  }
  return B + multiply(A - 1, B);
};

const multiply = function (A, B) {
  // 减少递归次数
  if (A > B) {
    return calculate(B, A);
  }
  return calculate(A, B);
};

const calculate = function (a, b) {
  if (a == 0) {
    return 0;
  }
  if (a == 1) {
    return b;
  }
  const halfA = a >> 1;
  const halfAResult = calculate(halfA, b);
  return halfAResult + halfAResult + (a & (1 == 1) ? b : 0);
};

function Foo (p) {
    // 边界条件
    if p then
      return
  end if
  // 调用自身递归
    Foo(p)
}

/**
 * 前序遍历 -- 递归写法
 */
function preOrder(TreeNode root) {
  if root == null then
      return
  end if

  // TODO: 前序遍历
  inOrder(root.left);
  inOrder(root.right);
}

/**
 * 前序遍历 -- 利用栈 迭代
 */
class Solution {
  void preOrder(TreeNode root) {
  }
}

/**
 *
 */
function inOrder(TreeNode root) {
  if root == null then
      return
  end if

  inOrder(root.left);
  // TODO 中序遍历
  inOrder(root.right);
}

/**
 * 中序遍历 -- 利用栈 迭代
 */
function inOrder(TreeNode root) {
  stack <- new Stack()
  current = root

  while current != null or !stack.isEmpty() do
    while current != null do
      stack.push(curr);
      curr = curr.left;
    end

    curr = stack.pop();
    // TODO 中序遍历
    curr = curr.right;
    end
}

/**
 * 后序遍历 -- 递归写法
 */
function postOrder(TreeNode root) {
  if root == null then
    return
  end if

  inOrder(root.left);
  inOrder(root.right);
  // TODO 后序遍历
}

/**
 * 后序遍历 -- 利用栈 迭代
 */
function postOrder (root) {
  const stack = [];
  let prev = null;

  while (root != null || stack.length > 0) {
    while (root != null) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    if (root.right == null || root.right === prev) {
      // TODO: 后序遍历
      prev = root
      root = null
    } else {
      stack.push(root)
      root = root.right
    }
  }
}

/**
 * 层序遍历 -- 利用队列辅助
 */
class Solution {
  void levelOrder(TreeNode root) {
  }
}

var maxDepth = function (root) {
  if (root == null) {
    return 0;
  }
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};

function fib(N) {
  if (N === 1 || N === 2) return 1;
  return fib(N - 1) + fib(N - 2);
}

class SolutionWithHashMap {
  public int fib(int N) {
    if (N < 1) {
      return 0;
    }

    HashMap<Integer, Integer> memo = new HashMap<>();

    return helper(memo, N);
  }

  int helper (HashMap<Integer, Integer> memo, int N) {
    if (N == 0) {
      return 0;
    }
    if (N == 1 || N == 2) {
      return 1;
    }

    if (memo.get(N) != null) {
      return memo.get(N);
    }
    memo.put(N, helper(memo, N - 1) + helper(memo, N - 2));
    return memo.get(N);
  }
}

class SolutionWithDpTable {
  public int fib(int N) {
    ArrayList<Integer> dp = new ArrayList<>(N + 1);

    dp.add(0);
    dp.add(1);
    dp.add(1);

    for (int i = 3; i <= N; i++) {
      dp.add(dp.get(i - 1) + dp.get(i - 2));
    }
    return dp.get(N);
  }
}

class Solution {
  public int fib(int N) {
    if (N == 0) return 0;
    if (N == 1 || N == 2) return 1;

    int prev = 1;
    int curr = 1;

    for (int i = 3; i <= N; i++) {
      int sum = prev + curr;
      prev = curr;
      curr = sum;
    }
    return curr;
  }
}

/**
 * 暴力遍历
 */
class SolutionDp {
  public int coinChange(int[] coins, int amount) {
    if (amount == 0) {
      return 0;
    }
    return getMinCoinNumber(coins, amount, 0);
  }

  int getMinCoinNumber (int[] coins, int amount, int num) {
    int res = Integer.MAX_VALUE;
    int nothingNum = 0;

    for (int i = 0; i < coins.length; i++) {
      int nextAmount = amount - coins[i];

      if (nextAmount == 0) {
        res = Math.min(res, num + 1);
      } else if (nextAmount < 0) {
        // -1
        nothingNum += 1;
      } else {
        res = Math.min(res, getMinCoinNumber(coins, nextAmount, num + 1));
      }
    }
    if (nothingNum == coins.length) {
      return -1;
    }
    return res;
  }
}

/**
 * 带备忘录的递归（自上而下）
 */
class SolutionDpWidthMemo {
  public int coinChange(int[] coins, int amount) {
    HashMap<Integer, Integer> memo = new HashMap<>();
    return dp(coins, amount, memo);
  }

  int dp (int[] coins, int amount, HashMap<Integer, Integer> memo) {
    // base case
    if (amount == 0) {
      return 0;
    }
    if (amount < 0) {
      return -1;
    }

    if (memo.get(amount) != null) {
      return memo.get(amount);
    }

    int res = Integer.MAX_VALUE;
    for (int i = 0; i < coins.length; i++) {
      int subProblem = dp(coins, amount - coins[i], memo);
      if (subProblem == -1) {
        continue;
      }
      res = Math.min(res, subProblem + 1);
    }

    if (res == Integer.MAX_VALUE) {
      memo.put(amount, -1);
      return -1;
    }
    memo.put(amount, res);

    return res;
  }

class Solution {
  public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);

    dp[0] = 0;

    for (int i = 1; i < dp.length; i++) {
      for (int coin : coins) {
        if (i - coin < 0) {
          continue;
        }
        dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
      }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
  }
}