LeetCode 1105. 填充书架（DP）

输入：books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], 
	shelf_width = 4
输出：6
解释：
3 层书架的高度和为 1 + 3 + 2 = 6 。
第 2 本书不必放在第一层书架上。
 
提示：
1 <= books.length <= 1000
1 <= books[i][0] <= shelf_width <= 1000
1 <= books[i][1] <= 1000

class Solution {
public:
    int minHeightShelves(vector<vector<int>>& books, int shelf_width) {
        int n = books.size();
        vector<int> dp(n+1, INT_MAX);
        dp[0] = 0;//没有书的时候
        for(int i = 1; i <= n; ++i)
        {
            int w = 0, h = 0;
            for(int j = i; j > 0; --j)
            {
                if(w+books[j-1][0] <= shelf_width)
                {	// 这一层还能放前面的书
                    h = max(h, books[j-1][1]);//这层的高度
                    w += books[j-1][0];//这层的宽度
                    dp[i] = min(dp[j-1]+h, dp[i]);
                    //     上一层的最右侧是 j-1 书籍，最低书架高度是 dp[j-1]
                    //   加上当前层的高度 h 
                }
                else
                    break;
            }
        }
        return dp[n];
    }
};