package com.sunny.grokkingalgorithms.fasttrack.dynamicprogrammingandrecursion;

/**
 * Created by sundas on 6/15/2018.
 */
public class RodCuttingProblem {

  /*
  Given a ro of certain length and the price at cutting each
  rod at different lengths. How will we maximise profit for the rod cutting.
  For example:
  length = 1 2 3 4 5 6 7 8
  price = 1 5 8 9 10 17 17 20
  if we sell the rod of length 4 without cutting we get 9
  if we cut the rod in two pieces of length 2 each
  we get 10
   */

  static int[] rodCuttingCache;

  public static int
  rodCuttingMemoized(int[] length,int[] price,int rodLength){
    if(rodCuttingCache[rodLength] >= 0){
      return rodCuttingCache[rodLength];
    }
    if(rodLength == 0){
      //System.out.println(path);
      //System.out.println(currentPrice);
      return 0;
    }
    //System.out.println(currentLength);
    //currentPrice += price[currentLength];
    int maxPrice = Integer.MIN_VALUE;
    for(int i = 1; i <= rodLength ; i++){
      maxPrice = Math.max(maxPrice,rodCuttingMemoized(length,price,
          rodLength - length[i]) + price[length[i]]);
    }
    rodCuttingCache[rodLength] = maxPrice;
    return maxPrice;
  }


  /**
   *
   * @param length
   * @param price
   * @param rodLength
   * @return
   */
  public static int
     rodCutting(int[] length,int[] price,int rodLength){
    if(rodLength == 0){
      //System.out.println(path);
      //System.out.println(currentPrice);
      return 0;
    }
    //System.out.println(currentLength);
    //currentPrice += price[currentLength];
    int maxPrice = Integer.MIN_VALUE;
    for(int i = 1; i <= rodLength ; i++){
      maxPrice = Math.max(maxPrice,rodCutting(length,price,
          rodLength - length[i]) + price[length[i]]);
    }
    return maxPrice;
  }

  /**
   *
   * @param args
   */
  public static void main(String[] args) {
    int[] length = new int[]{0,1,2,3,4,5,6,7,8};
    int[] price = new int[]{0,1,5,8,9,10,17,17,20};
    /*
    For rod of length 4
    we can get 10 (2*5)
     */
    rodCuttingCache = new int[length.length];
    for(int i = 0 ; i < rodCuttingCache.length ; i++){
      rodCuttingCache[i] = -1;
    }
    System.out.println(rodCutting(length, price, 4));
    //System.out.println(rodCuttingAlternate(length,price,4,0));
    System.out.println(rodCuttingMemoized(length,price,4));
  }

}

@@ -526,16 +526,615 @@
 Cache;%0A%0A
+  /**%0A   *%0A   * @param length%0A   * @param price%0A   * @param rodLength%0A   * @return%0A   */%0A  public static int rodCuttingDP(int%5B%5D length,int%5B%5D price,int rodLength)%7B%0A    int%5B%5D maxValues = new int%5BrodLength + 1%5D;%0A    for(int i = 1; i %3C= rodLength ; i++)%7B%0A      maxValues%5Bi%5D = Integer.MIN_VALUE;%0A      for(int j = 1; j %3C= i ; j++)%7B%0A        maxValues%5Bi%5D = Math.max(maxValues%5Bi%5D,%0A            price%5Bj%5D +%0A        maxValues%5Bi - j%5D);%0A      %7D%0A    %7D%0A    for(int i = 0 ; i %3C maxValues.length ;i++)%7B%0A      System.out.print(maxValues%5Bi%5D + %22 %22);%0A    %7D%0A    System.out.println();%0A    return maxValues%5BrodLength%5D;%0A  %7D%0A%0A
   public
@@ -2937,15 +2937,158 @@
 ce,4));%0A
+    //length = new int%5B%5D%7B1,2,3,4,5,6,7,8%7D;%0A    //price = new int%5B%5D%7B1,5,8,9,10,17,17,20%7D;%0A    System.out.println(rodCuttingDP(length,price,4));%0A
   %7D%0A%0A%7D%0A

Rodcutting problem using dp. O(n.square(2))