【C++动态规划】1105. 填充书架|2104

本文涉及知识点

下载及打开打包代码的方法兼述单元测试
C++动态规划

LeetCode1105. 填充书架

给定一个数组 books ，其中 books[i] = [thicknessi, heighti] 表示第 i 本书的厚度和高度。你也会得到一个整数 shelfWidth 。
按顺序 将这些书摆放到总宽度为 shelfWidth 的书架上。
先选几本书放在书架上（它们的厚度之和小于等于书架的宽度 shelfWidth ），然后再建一层书架。重复这个过程，直到把所有的书都放在书架上。
需要注意的是，在上述过程的每个步骤中，摆放书的顺序与给定图书数组 books 顺序相同。
例如，如果这里有 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

动态规划

动态规划的状态表示

dp[i]已经处理了前i本书的最小高度。 空间复杂度：O(n)

动态规划的填表顺序

枚举前置状态，第一层循环：i从0到n-1，第二次循环，枚举当前层是第i到第j本。

动态规划的转移方程

dp[j+1] = min(dp[j+1],dp[i]+max(第[i…j]本书的高度)

动态规划的初始值

dp[0]=0 ，其它全为INT_MAX/2。

动态规划的返回值

dp.back()

代码

核心代码

class Solution {
		public:
			int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
				const int N = books.size();
				vector<int> dp(N + 1, INT_MAX / 2);
				dp[0] = 0;
				for (int i = 0; i < N; i++) {
					int iMax = 0, iWidth = 0;
					for (int j = i; j < N; j++) {
						iMax = max(iMax, books[j][1]);
						iWidth += books[j][0];
						if (iWidth > shelfWidth)break;
						dp[j + 1] = min(dp[j + 1], dp[i] + iMax);
					}
				}
				return dp.back();
			}
		};

单元测试

vector<vector<int>> books;
		int shelfWidth;
		TEST_METHOD(TestMethod11)
		{
			books = { {1,1},{2,3},{2,3},{1,1},{1,1},{1,1},{1,2} }, shelfWidth = 4;
			auto res = Solution().minHeightShelves(books, shelfWidth);
			AssertEx(6, res);
		}
		TEST_METHOD(TestMethod12)
		{
			books = { {1,3},{2,4},{3,2} }, shelfWidth = 6;
			auto res = Solution().minHeightShelves(books, shelfWidth);
			AssertEx(4, res);
		}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。