leetcode IntegerReplacement

import java.util.Hashtable;

public class IntegerReplacement {
  /**
   * Given a positive integer n and you can do operations as follow:
   *
   * If n is even, replace n with n/2.
   * If n is odd, you can replace n with either n + 1 or n - 1.
   * What is the minimum number of replacements needed for n to become 1?
   *
   * Example 1:
   *
   * Input:
   * 8
   * Output:
   * 3
   * Explanation:
   * 8 -> 4 -> 2 -> 1
   *
   * Example 2:
   * Input:
   * 7
   * Output:
   * 4
   * Explanation:
   * 7 -> 8 -> 4 -> 2 -> 1
   * or
   * 7 -> 6 -> 3 -> 2 -> 1
   */

  // dp methods may get a correct answer but will get a memory exceed
  public int solutionDP(int n){
    int[] dp = new int[n+1];
    dp[1] = 0;
    dp[2] = 1;
    for (int i=3; i<n; i++){
      if (i%2 == 0){
        dp[i] = dp[i/2] + 1;
      }
      else{
        dp[i] = Math.min(dp[(i-1)/2]+1, dp[(i+1)/2]+2);
      }
    }
    return dp[n];
  }

  // 用递归的方式
  public int solutionRecuitive(int n){
    if (n == 1) return 0;
    if (n == 2) return 1;
    else{
      if (n%2 == 0){
        return solutionRecuitive(n/2) + 1;
      }
      else {
        return Math.min(solutionRecuitive(n - 1) + 1, solutionRecuitive((n + 1) / 2) + 2); // 这里n+1可能会造成溢出，应该换成1 +（n-1）/2
      }
    }
  }

  // 进一步优化，可以使用哈希表来存储已经计算过的中间变量
  public int solutionHashTable(int n){
    Hashtable<Integer, Integer> ht = new Hashtable<>();
    ht.put(1, 0);
    ht.put(2, 1);

    helper(n, ht);
    return ht.get(n);
  }

  public int helper(int n, Hashtable<Integer, Integer> ht){
    if (ht.containsKey(n)) return ht.get(n);

    int step;
    if (n%2 == 0){
      step = helper(n/2, ht) + 1;
    }
    else
      step = Math.min(helper(n-1, ht)+1, helper((n+1)/2, ht)+2);
    ht.put(n, step);
    return step;
  }

}