Filling Bookcase Shelves LeetCode solution in C++

1
class Solution {
2
 public:
3
  int minHeightShelves(vector<vector<int>> &books, int shelfWidth) {
4
    int n = books.size();
5
    vector<vector<int>> cost(n + 1, vector<int>(n + 1));
6
    for (int i = 1; i <= n; i++) {
7
      int height = books[i - 1][1];
8
      int width = books[i - 1][0];
9
      cost[i][i] = height;
10
      for (int j = i + 1; j <= n; j++) {
11
        height = max(height, books[j - 1][1]);
12
        width += books[j - 1][0];
13
        if (width <= shelfWidth)
14
          cost[i][j] = height;
15
        else
16
          cost[i][j] = -1;
17
      }
18
    }
19
    vector<int> ans(n + 1);
20
    ans[0] = 0;
21
    for (int i = 1; i <= n; i++) {
22
      ans[i] = INT_MAX;
23
      for (int j = 1; j <= i; j++) {
24
        if (cost[j][i] == -1) continue;
25
        if (ans[j - 1] != INT_MAX) ans[i] = min(ans[i], ans[j - 1] + cost[j][i]);
26
      }
27
    }
28
    return ans[n];
29
  }
30
};