1105. Filling Bookcase Shelves

 JAVA

• class Solution {
      public int minHeightShelves(int[][] books, int shelfWidth) {
          int n = books.length;
          int[] f = new int[n + 1];
          for (int i = 1; i <= n; ++i) {
              int w = books[i - 1][0], h = books[i - 1][1];
              f[i] = f[i - 1] + h;
              for (int j = i - 1; j > 0; --j) {
                  w += books[j - 1][0];
                  if (w > shelfWidth) {
                      break;
                  }
                  h = Math.max(h, books[j - 1][1]);
                  f[i] = Math.min(f[i], f[j - 1] + h);
              }
          }
          return f[n];
      }
  }

C++

• class Solution {
  public:
      int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
          int n = books.size();
          int f[n + 1];
          f[0] = 0;
          for (int i = 1; i <= n; ++i) {
              int w = books[i - 1][0], h = books[i - 1][1];
              f[i] = f[i - 1] + h;
              for (int j = i - 1; j > 0; --j) {
                  w += books[j - 1][0];
                  if (w > shelfWidth) {
                      break;
                  }
                  h = max(h, books[j - 1][1]);
                  f[i] = min(f[i], f[j - 1] + h);
              }
          }
          return f[n];
      }
  };