题：
https://leetcode-cn.com/problems/filling-bookcase-shelves/
解1（超时）：
public static int minHeightShelves(int[][] books, int shelf_width) {int[] minHigh = new int[]{Integer.MAX_VALUE};dfs(minHigh,0,books,shelf_width,0);return minHigh[0];}/*** 超时解法：* 深搜，每层放一本书、两本书、...直到该层厚度为shelf_width* @param minHigh 最小整体高度* @param currentHigh 当前整体高度* @param books 书的数组* @param shelf_width 书架宽度* @param curIndex 当前数组下标,还没放的第一本书*/public static void dfs(int[] minHigh,int currentHigh,int[][] books , int shelf_width , int curIndex){if(curIndex == books.length){minHigh[0] = Math.min(minHigh[0],currentHigh);return;}int curWidth = 0; // 当前层宽度int currentLevelHigh = 0; // 当前层高度for(int i = curIndex ; i < books.length ; i++){curWidth+=books[i][0];if(curWidth > shelf_width)break;else{currentLevelHigh = Math.max(currentLevelHigh,books[i][1]); // 更新当前层最高的高度dfs(minHigh,currentHigh+currentLevelHigh,books,shelf_width,i+1);}}}
解2（动态规划）：
public static int minHeightShelves(int[][] books, int shelf_width) {/*** dp表示 只考虑前i本书的时候，书架最小高度* */int[] dp = new int[books.length];dp[0] = books[0][1];//dp[1] = books[0][0]+books[0][1] > shelf_width?dp[0]+books[1][1]:Math.max(dp[0],books[1][1]);for(int i = 1 ; i < books.length ; i++){dp[i] = dp[i-1] + books[i][1];int levelWidth = books[i][0];int levelHigh = books[i][1];for(int j = i - 1 ; j >= 0 ; j--){levelWidth+=books[j][0];if(levelWidth <= shelf_width){levelHigh = Math.max(levelHigh,books[j][1]);dp[i] = j-1>=0?Math.min(dp[i],dp[j-1]+levelHigh):levelHigh;}else break;}}return dp[books.length-1];}