填充书架【LC1105】
给定一个数组
books，其中books[i] = [thicknessi, heighti]表示第i本书的厚度和高度。你也会得到一个整数shelfWidth。按顺序 将这些书摆放到总宽度为
shelfWidth的书架上。先选几本书放在书架上（它们的厚度之和小于等于书架的宽度
shelfWidth），然后再建一层书架。重复这个过程，直到把所有的书都放在书架上。需要注意的是，在上述过程的每个步骤中，摆放书的顺序与你整理好的顺序相同。
- 例如，如果这里有 5 本书，那么可能的一种摆放情况是：第一和第二本书放在第一层书架上，第三本书放在第二层书架上，第四和第五本书放在最后一层书架上。
每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。
以这种方式布置书架，返回书架整体可能的最小高度。
小忙 写简略点
dfs+记忆化：选或不选
- 思路：
感觉递推的形式不是很好写，所以一开始的想法是dfs+记忆化。每遇到一本书，我们可以选择新建一层放置这本书，也可以选择在上一次继续放置这本书，影响结果的有两个因素：该层已经摆放的书的宽度以及最大高度。因此在dfs过程需要记录这两个值，定义
class Solution { int[][] dp; int[][] books; int shelfWidth; public int minHeightShelves(int[][] books, int shelfWidth) { int n = books.length; dp = new int[n + 1][shelfWidth + 1]; this.books = books; this.shelfWidth = shelfWidth; return dfs(0, 0, 0); } public int dfs(int i, int width, int maxHeight){ if (i == books.length) return maxHeight; if (dp[i][width] != 0) return dp[i][width]; // 新建一层 int res = maxHeight + dfs(i + 1, books[i][0], books[i][1]); // 如果宽度满足要求 那么可以继续往后面放 if (width + books[i][0] <= shelfWidth){ res = Math.min(res, dfs(i + 1, width +books[i][0], Math.max(maxHeight, books[i][1]))); } dp[i][width] = res; return res; } }
dfs+记忆化：枚举选到哪个
- 实现：
class Solution { int[] dp; int[][] books; int shelfWidth; public int minHeightShelves(int[][] books, int shelfWidth) { int n = books.length; dp = new int[n + 1]; this.books = books; this.shelfWidth = shelfWidth; return dfs(0); } public int dfs(int i){ if (i == books.length) return 0; if (dp[i] != 0) return dp[i]; int width = 0, maxHeight = 0, res = Integer.MAX_VALUE; for (int j = i; j < books.length; j++){ width += books[j][0]; if (width > shelfWidth) break;// 无法放书 maxHeight = Math.max(maxHeight, books[j][1]); res = Math.min(res, dfs(j + 1) + maxHeight); } dp[i]= res; return res; } }
class Solution { public int minHeightShelves(int[][] books, int shelfWidth) { int n = books.length; int[] dp = new int[n + 1]; for (int i = 0; i < n; i++){ int w = books[i][0], h = books[i][1]; dp[i + 1] = dp[i] + h;// 独立一层 for (int j = i - 1; j >= 0; j--){// 枚举可以选哪个 w += books[j][0]; if (w > shelfWidth) break; h = Math.max(h, books[j][1]); dp[i + 1] = Math.min(dp[i + 1], dp[j] + h); } } return dp[n]; } }
