1105. Filling Bookcase Shelves

Link

Solution

    int width;
    int[][] memo = new int[1001][1001];
    public int minHeightShelves(int[][] books, int shelf_width) {
        width = shelf_width;
        return helper(books, 0, 0, shelf_width);
    }
    
    public int helper(int[][] books, int i, int shelf_height ,int remain_width){
        
        if(i >= books.length) return shelf_height;
        if(memo[i][remain_width] != 0) return memo[i][remain_width];
        
        //new level
        if(remain_width < books[i][0]){
            memo[i][remain_width] = shelf_height + helper(books, i+1, books[i][1], width-books[i][0]);
        }
        else{
            if(shelf_height >= books[i][1]){
                memo[i][remain_width] = helper(books, i+1, shelf_height, remain_width - books[i][0]);
            }
            else{
                memo[i][remain_width] = Math.min(helper(books, i+1, 
                                       books[i][1], remain_width - books[i][0]) 
                                , shelf_height 
                                + helper(books, i+1, books[i][1], width-books[i][0]));
            }
        }
        return memo[i][remain_width];
        
    }