LC-1105. 填充书架（记忆化搜索 ==＞ 动态规划）

1105. 填充书架

难度中等169

给定一个数组 books ，其中 books[i] = [thicknessi, heighti] 表示第 i 本书的厚度和高度。你也会得到一个整数 shelfWidth 。

按顺序 将这些书摆放到总宽度为 shelfWidth 的书架上。

先选几本书放在书架上（它们的厚度之和小于等于书架的宽度 shelfWidth ），然后再建一层书架。重复这个过程，直到把所有的书都放在书架上。

需要注意的是，在上述过程的每个步骤中，摆放书的顺序与你整理好的顺序相同。

• 例如，如果这里有 5 本书，那么可能的一种摆放情况是：第一和第二本书放在第一层书架上，第三本书放在第二层书架上，第四和第五本书放在最后一层书架上。

每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。

以这种方式布置书架，返回书架整体可能的最小高度。

示例 1：

输入：books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4
输出：6
解释：
3 层书架的高度和为 1 + 3 + 2 = 6 。
第 2 本书不必放在第一层书架上。

示例 2:

输入: books = [[1,3],[2,4],[3,2]], shelfWidth = 6
输出: 4

提示：

• 1 <= books.length <= 1000
• 1 <= thicknessi <= shelfWidth <= 1000
• 1 <= heighti <= 1000

记忆化搜索 ==> 递推

题解：https://leetcode.cn/problems/filling-bookcase-shelves/solution/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-0vg6/

记忆化

class Solution {int[][] books;int[] cache;int shelfWidth;public int minHeightShelves(int[][] books, int shelfWidth) {this.books = books;this.shelfWidth = shelfWidth;// 举个例子，[把 books[n -1] 单独放一层，把 books[n - 2] 单独放1层和[把 books[n - 2] 和 books[n -1]放同一层] ，都会递归到dfs(n - 3)。// 一叶知秋，整个递归中有大量重复递归调用（递归入参相同cache = new int[books.length]; Arrays.fill(cache, -1);return dfs(books.length - 1);}/**定义dfs(i) 表示把books[0]到books[i]按顺序摆放后的最小高度枚举最后一层的第一本书的下标j，那么从books[j]到books[i]的宽度之和不能超过shelfWidth状态转移方程：dfs(i) = min{dfs(j-1) + max(books[k][1])}, j <= k= i递归边界：dfs(-1) = 0，没有书，最小高度为0递归入口：dfs(n-1) 表示把书按顺序拜访后的最小高度 */public int dfs(int i){if(i < 0) return 0; // 没有书了， 高度为0if(cache[i] >= 0) return cache[i];int res = Integer.MAX_VALUE, maxH = 0,leftW = shelfWidth;for(int j = i; j >= 0; j--){leftW -= books[j][0];if(leftW < 0) break; // 空间不足，无法放书maxH = Math.max(books[j][1], maxH); // 从j到i的最大高度res = Math.min(res, dfs(j-1) + maxH);}return cache[i] = res;}
}

转成递推

class Solution {public int minHeightShelves(int[][] books, int shelfWidth) {int n = books.length;int[] f = new int[n+1];// 由于需要一个状态标识i<0，因此整体右移，最后答案返回f[n]f[0] = 0; // 初始值：没有书时最小高度为0 for(int i = 0; i < n; i++){f[i+1] = Integer.MAX_VALUE; // 初始高度无穷大（res，因为求最小高度）int maxH = 0, leftW = shelfWidth;for(int j = i; j >= 0; j--){leftW -= books[j][0];if(leftW < 0) break; // 空间不足，无法放书maxH = Math.max(maxH, books[j][1]); // 从 j 到 i 的最大高度f[i+1] = Math.min(f[i+1], f[j] + maxH);}}return f[n];}
}