非常经典的动态规划的题
可以写出状态转移方程
如果当前书放在新的一行
dp[i + 1] = dp[i] + h
如果当前书没有放在新的一行
dp[i + 1] = min(所有的倒数 n 本书在最后一行的各种情况)
const minHeightShelves = function (books, shelf_width) {
const dp = [0];
let t, h;
for (let i = 0; i < books.length; i++) {
t = books[i][0];
h = books[i][1];
dp[i + 1] = dp[i] + h;
for (let j = i - 1; j >= 0; j--) {
t += books[j][0];
h = Math.max(h, books[j][1]);
if (t > shelf_width) {
break;
}
dp[i + 1] = Math.min(dp[i + 1], dp[j] + h);
}
}
return dp[books.length];
};