Computes minimum number of multiplication required to compute the nth power of a number

PowerOfPowers.java

/* File:    PowerOfPowers.java
 * Created: 2018-05-26
 * Author:  Sabbir Manandhar
 *
 * Copyright (c) 2018 Hogwart Inc.
 */

import java.io.*;
import java.util.*;

/**
 * Computes minimum number of multiplication required to compute the nth power of a number
 *
 * @author Sabbir Manandhar
 * @version 1.0
 */
public class PowerOfPowers {
  /**
  * Driver method
  */
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter the value of n:" + compute(sc.nextInt()));
  } // main
  
  //---------------------------------------------------------------------------

  /**
  * Computes the minimum number of mulitplication
  * using bottom dynamic programming
  * @param 
  */
  public static int compute(int n) {
    int[] dp = new int[n + 1];
    for (int i = 0; i <= n; i++) {
      dp[i] = helper(i, dp);
    }
    return dp[x];
  } // compute
  
  //---------------------------------------------------------------------------

  /**
  * helper method that computes miniumum number of multplications
  * required to compute nth power of a number. It uses previous 
  * results to compute the value
  *
  * @param n nth power to compute
  * @param dp previous results
  */
  public static int helper(int n, int[] dp) {
    int[] baseCases = new int[]{0, 0, 1, 2, 2};
    if (n <= 3) return baseCases[n];

    int min = Integer.MAX_VALUE;
    if (n % 2 == 0) return dp[n / 2] + 1; // even n
    for (int i = 2; i <= n / 2; i++) {
      int part1 = (i - 1) + dp[n / i];
      int part2 = dp[n % i];
      int result = part1 + part2 + (n % i == 0 ? 0 : 1);
      min = Math.min(result, min);
    }
    return min;
  } // helper
  
} // PowerOfPowers