1105.填充书架.md

1105.填充书架

/*
 * @lc app=leetcode.cn id=1105 lang=typescript
 *
 * [1105] 填充书架
 */

// @lc code=start
function minHeightShelves(books: number[][], shelfWidth: number): number {}
// @lc code=end

解法 1: 动态规划

function minHeightShelves(books: number[][], shelfWidth: number): number {
  const n = books.length,
    dp = new Array(n).fill(Infinity)
  for (let i = 0; i < n; i++) {
    let max = books[i][1],
      w = books[i][0]
    dp[i] = (dp[i - 1] ?? 0) + max
    for (let j = i - 1; j >= 0; j--) {
      w += books[j][0]
      if (w > shelfWidth) break
      max = Math.max(books[j][1], max)
      dp[i] = Math.min(dp[i], (dp[j - 1] ?? 0) + max)
    }
  }
  return dp[n - 1]
}

Case

test.each([
  {
    input: {
      books: [
        [1, 1],
        [2, 3],
        [2, 3],
        [1, 1],
        [1, 1],
        [1, 1],
        [1, 2],
      ],
      shelfWidth: 4,
    },
    output: 6,
  },
  {
    input: {
      books: [
        [1, 3],
        [2, 4],
        [3, 2],
      ],
      shelfWidth: 6,
    },
    output: 4,
  },
])('input: books = $input.books, shelfWidth = $input.shelfWidth', ({ input: { books, shelfWidth }, output }) => {
  expect(minHeightShelves(books, shelfWidth)).toEqual(output)
})