郑州网站建设zhuotop,无障碍网站建设方案,代码生成器app下载手机版,陶瓷网站建设中企动力想要精通算法和SQL的成长之路 - 填充书架 前言一. 填充书架1.1 优化 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 填充书架
原题链接
题目中有一个值得注意的点就是#xff1a;
需要按照书本顺序摆放。每一层当中#xff0c;只要厚度不够了#xff0c;当前层最高… 想要精通算法和SQL的成长之路 - 填充书架 前言一. 填充书架1.1 优化 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 填充书架
原题链接
题目中有一个值得注意的点就是
需要按照书本顺序摆放。每一层当中只要厚度不够了当前层最高的那一本书籍就视为本层的高度。
那么我们假设dp[i] 代表从 book[0] 摆到 book[i] 的时书架的最小高度。
假设最后一层的第一本书的下标是 j那么之前所有书本摆放的最小高度就是 dp[j-1]。我们再计算出下标在[j,i]最后一层的书本中高度最高的那一本书同时满足厚度不超过shelfWidth高度为maxHeight。那么当前的最小总高度是 res Max(dp[i-1]maxHeightres)。即之前的总高度最后一层的最高高度。
我们递归从后往前递归。入参为遍历的书本下标。
终止条件下标 0。代表没有书本了停止递归。递归做的事情循环[0,i]之间的所有元素从后往前把书本放入最后一层一旦厚度超出终止遍历。否则计算当前层的最高高度以及最小总高。
public class Test1105 {public int[][] books;public int shelfWidth;public int minHeightShelves(int[][] books, int shelfWidth) {this.books books;this.shelfWidth shelfWidth;return dfs(books.length - 1);}public int dfs(int i) {// 终止条件if (i 0) {return 0;}int res Integer.MAX_VALUE, maxHeight 0, width shelfWidth;for (int j i; j 0; j--) {// 从后往前放书本width - books[j][0];// 厚度不能超过 shelfWidth 超过就代表放不下了if (width 0) {break;}// 当前层最高高度maxHeight Math.max(maxHeight, books[j][1]);// 更新总最低书架高度 上层最小总高度 当前层最高高度res Math.min(res, dfs(j - 1) maxHeight);}return res;}
}这个解答其实对于用例比较多的情况是会超时的。
1.1 优化
我们来看下上面代码的不好的点
每次dfs的时候循环的范围是[0,j]。循环内部又每次调用了dfs递归即dfs[j-1]。
整个递归函数只用到了一个索引的参数我们可以发现索引为1,2,3…的递归被重复调用了非常多次。以当前索引为3为例
第一次递归范围[0,3]。第二次递归范围[0,2]。第三次递归范围[0,1]。…
那么我们可以用一个全局的变量去记录每次dfs返回的结果即可:
public class Test1105 {public int[][] books;public int shelfWidth;// 缓存dfs的结果public int[] dfsCache;public int minHeightShelves(int[][] books, int shelfWidth) {this.books books;this.shelfWidth shelfWidth;// 初始化dfsCache new int[books.length];// 给个初始值-1代表没有被执行过即没有缓存Arrays.fill(dfsCache, -1);return dfs(books.length - 1);}public int dfs(int i) {// 终止条件if (i 0) {return 0;}// 如果是-1代表这层值没有执行过往下走。否则说明有缓存了直接返回if (dfsCache[i] ! -1) {return dfsCache[i];}int res Integer.MAX_VALUE, maxHeight 0, width shelfWidth;for (int j i; j 0; j--) {// 从后往前放书本width - books[j][0];// 厚度不能超过 shelfWidth 超过就代表放不下了if (width 0) {break;}// 当前层最高高度maxHeight Math.max(maxHeight, books[j][1]);// 更新总最低书架高度 上层最小总高度 当前层最高高度res Math.min(res, dfs(j - 1) maxHeight);}// 缓存下当前结果dfsCache[i] res;return dfsCache[i];}
}
