1105. 填充书架

发表于 分类于 阅读次数： Waline： 本文字数： 144 阅读时长 ≈ 1 分钟

考点

  • 划分DP

思路

直接看代码即可，是一道划分DP的裸题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
    // 将数组划分为若干个连续的子数组
    // 每个子数组的thick和小于等于shelfWidth
    // 求所有子数组的max(height)的和的最小值
    int f[1005], n = books.size();
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
      int s = 0, j = i, mx = 0;
      while (j >= 1 && s < shelfWidth) {
        int x = books[j - 1][0];
        if (s + x > shelfWidth) break;
        s += x;
        mx = max(mx, books[j - 1][1]);
        f[i] = min(f[i], mx + f[j - 1]);
        --j;
      }
    }
    return f[n];
  }
};