Advertisement
ven4coding

Cutting Rods Iterative with tabulation

Aug 22nd, 2020
217
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 0.89 KB | None | 0 0
  1. import java.util.Arrays;
  2.  
  3. public class CurRodIterative {
  4.     public static void main(String[] args) {
  5.         int n = 5;
  6.         int[] tab = new int[n + 1];
  7.         int[] priceArr = new int[]{1, 5, 8, 9, 10, 17, 17, 20};
  8.         Arrays.fill(tab, -1);
  9.         tab[0] = 0;
  10.         int maxPrice;
  11.         for (int i = 0; i <= n; i++) {
  12.             if (i == 0) {
  13.                 continue;
  14.             }
  15.             maxPrice = -1;
  16.             for (int j = 1; j <= i; j++) {
  17.                 // example priceArr[1]+mem[0].
  18.                 int currentPrice = priceArr[j - 1] + tab[i - j];
  19.                 maxPrice = Math.max(currentPrice, maxPrice);
  20.             }
  21.             System.out.println("max price of rod of size " + i + " is " + maxPrice);
  22.             tab[i] = maxPrice;
  23.         }
  24.         System.out.format("Maximum price by selling pieces of %d size rod is %d", n, tab[n]);
  25.     }
  26. }
  27.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement