Advertisement
ven4coding

Cutting Rods Recursive with memoization

Aug 22nd, 2020
1,053
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 0.73 KB | None | 0 0
  1. import java.util.Arrays;
  2.  
  3. public class CutRod {
  4.     public static void main(String[] args) {
  5.         int n = 5;
  6.         int[] mem = new int[n + 1];
  7.         Arrays.fill(mem, -1);
  8.         mem[0] = 0;
  9.         System.out.println(cut(new int[]{1, 5, 8, 9, 10, 17, 17, 20}, n, mem));
  10.     }
  11.  
  12.     private static int cut(int[] priceArr, int n, int[] mem) {
  13.         if (n == 0) {
  14.             return 0;
  15.         }
  16.  
  17.         int maxPrice = 0;
  18.  
  19.         for (int i = 0; i < n; i++) {
  20.             if (mem[i] == -1) {
  21.                 mem[i] = cut(priceArr, i, mem);
  22.             }
  23.             int currentPrice = priceArr[n - i - 1] + mem[i];
  24.             maxPrice = Math.max(currentPrice, maxPrice);
  25.         }
  26.  
  27.         return maxPrice;
  28.     }
  29. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement