package leetcode;

/**
 * https://leetcode.com/problems/filling-bookcase-shelves/
 */
public class Problem1105 {
    public int minHeightShelves(int[][] books, int shelf_width) {
        return minHeightShelves(books, shelf_width, 0, 0, 0);
    }

    private static int minHeightShelves(int[][] books, int shelfWidth,
                                        int totalWidth, int maxHeight, int index) {
        if (index == books.length) {
            return maxHeight;
        }
        int width = books[index][0];
        int height = books[index][1];
        if (totalWidth + width <= shelfWidth) {
            int a = minHeightShelves(books, shelfWidth, totalWidth + width,
                Math.max(maxHeight, height), index + 1);
            int b = minHeightShelves(books, shelfWidth, width, height, index + 1) + maxHeight;
            return Math.min(a, b);
        }
        return minHeightShelves(books, shelfWidth, width, height, index + 1) + maxHeight;
    }

    public static void main(String[] args) {
        Problem1105 prob = new Problem1105();
        System.out.println(prob.minHeightShelves(new int[][]{
            {1, 1}, {2, 3}, {2, 3}, {1, 1}, {1, 1}, {1, 1}, {1, 2}
        }, 4)); // 6
        System.out.println(prob.minHeightShelves(new int[][]{
            {1, 1}, {2, 3}, {2, 3}, {1, 1}, {1, 1}, {1, 1}, {1, 2}
        }, 8)); // 4
        System.out.println(prob.minHeightShelves(new int[][]{
            {1, 1}, {2, 3}, {2, 3}, {1, 1}, {1, 1}, {1, 1}, {1, 2}, {2, 4}, {3, 1}
        }, 4)); // 10
        System.out.println(prob.minHeightShelves(new int[][]{
            {1, 1}, {2, 3}, {2, 3}, {1, 1}, {1, 1}, {1, 1}, {1, 2}, {2, 4}, {3, 1}
        }, 7)); // 7
    }
}

@@ -231,16 +231,60 @@
  0, 0, 0
+, new Integer%5Bbooks.length%5D%5Bshelf_width + 1%5D
 );%0A    %7D
@@ -436,16 +436,74 @@
 nt index
+,%0A                                        Integer%5B%5D%5B%5D memo
 ) %7B%0A    
@@ -567,32 +567,133 @@
 ight;%0A        %7D%0A
+        if (memo%5Bindex%5D%5BtotalWidth%5D != null) %7B%0A            return memo%5Bindex%5D%5BtotalWidth%5D;%0A        %7D%0A
         int widt
@@ -751,16 +751,36 @@
 ex%5D%5B1%5D;%0A
+        int answer;%0A
         
@@ -949,16 +949,22 @@
 ndex + 1
+, memo
 );%0A     
@@ -1030,32 +1030,38 @@
 eight, index + 1
+, memo
 ) + maxHeight;%0A 
@@ -1071,22 +1071,24 @@
         
-return
+answer =
  Math.mi
@@ -1097,32 +1097,39 @@
 a, b);%0A        %7D
+ else %7B
 %0A        return 
@@ -1113,38 +1113,44 @@
  else %7B%0A        
-return
+    answer =
  minHeightShelve
@@ -1194,16 +1194,22 @@
 ndex + 1
+, memo
 ) + maxH
@@ -1223,734 +1223,78 @@
     
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem1105 prob = new Problem1105();%0A        System.out.println(prob.minHeightShelves(new int%5B%5D%5B%5D%7B%0A            %7B1, 1%7D, %7B2, 3%7D, %7B2, 3%7D, %7B1, 1%7D, %7B1, 1%7D, %7B1, 1%7D, %7B1, 2%7D%0A        %7D, 4)); // 6%0A        System.out.println(prob.minHeightShelves(new int%5B%5D%5B%5D%7B%0A            %7B1, 1%7D, %7B2, 3%7D, %7B2, 3%7D, %7B1, 1%7D, %7B1, 1%7D, %7B1, 1%7D, %7B1, 2%7D%0A        %7D, 8)); // 4%0A        System.out.println(prob.minHeightShelves(new int%5B%5D%5B%5D%7B%0A            %7B1, 1%7D, %7B2, 3%7D, %7B2, 3%7D, %7B1, 1%7D, %7B1, 1%7D, %7B1, 1%7D, %7B1, 2%7D, %7B2, 4%7D, %7B3, 1%7D%0A        %7D, 4)); // 10%0A        System.out.println(prob.minHeightShelves(new int%5B%5D%5B%5D%7B%0A            %7B1, 1%7D, %7B2, 3%7D, %7B2, 3%7D, %7B1, 1%7D, %7B1, 1%7D, %7B1, 1%7D, %7B1, 2%7D, %7B2, 4%7D, %7B3, 1%7D%0A        %7D, 7)); // 7
+%7D%0A        memo%5Bindex%5D%5BtotalWidth%5D = answer;%0A        return answer;
 %0A   

Solve problem 1105