书籍叠放

题目描述

书籍的长、宽都是整数对应 (l,w)。如果书A的长宽度都比B长宽大时，则允许将B排列放在A上面。现在有一组规格的书籍，书籍叠放时要求书籍不能做旋转，请计算最多能有多少个规格书籍能叠放在一起。

输入描述

输入：books = [[20,16],[15,11],[10,10],[9,10]]

说明：总共4本书籍，第一本长度为20宽度为16；第二本书长度为15宽度为11，依次类推，最后一本书长度为9宽度为10。

输出描述

输出：3

说明: 最多3个规格的书籍可以叠放到一起, 从下到上依次为: [20,16],[15,11],[10,10]

示例1

输入：
[[20,16],[15,11],[10,10],[9,10]]

输出：
3

题解

题目类型

这道题目属于动态规划（Dynamic Programming, DP）类型的算法题。动态规划适用于解决具有重叠子问题和最优子结构的问题，在这个问题中，我们通过构建一个 dp 数组来记录每个书籍最多能叠放多少本书。

解题思路

本题的核心在于判断哪些书籍可以叠放在其他书籍上，具体条件是长度和宽度都需要比其他书籍大。为了有效解决这个问题，我们可以采用以下步骤：

代码大致描述

1. 输入解析：首先从输入中读取书籍的尺寸信息，并解析成二维数组的形式。
2. 排序：将书籍按长、宽进行降序排序，这一步是为了方便后续的动态规划比较，避免遗漏可能的叠放顺序。
3. 动态规划：使用动态规划数组 dp 来记录每本书叠放的最大数量。对于每一对书籍，检查是否满足叠放条件，并更新 dp 数组。
4. 输出结果：通过 max(dp) 得到最大叠放数量。

C++

#include <bits/stdc++.h>

using namespace std;

// 解析二维数组
vector<vector<int>> parseMatrix(string &line) {
    vector<vector<int>> matrix;

    bool hasNum = false;
    int num = 0;
    vector<int> row;
    for (char c: line) {
        if (isdigit(c)) {
            num = num * 10 + c - '0';
            hasNum = true;
            continue;
        }

        if (hasNum) {
            row.push_back(num);
            hasNum = false;
            num = 0;
        }

        if (c == ']' && !row.empty()) {
            matrix.push_back(row);
            row.clear();
        }
    }

    return matrix;
}

int main() {
    string line;
    getline(cin, line);

    vector<vector<int>> books = parseMatrix(line);

    // 根据长宽降序排序
    sort(books.begin(), books.end(), [](auto &a, auto &b) {
        return a[0] != b[0] ? a[0] > b[0] : a[1] > b[1];
    });
    int n = books.size();
    // dp[i] 表示 books[i] 堆放在最上面时最多可以叠放的书本数
    vector<int> dp(n, 0);
    for (int r = 0; r < n; r++) {
        int leftMax = 0;
        for (int l = 0; l < r; l++) {
            // 判断 books[r] 本数是否可以堆放在 books[l] 书上面
            if (books[l][0] > books[r][0] && books[l][1] > books[r][1]) {
                leftMax = max(leftMax, dp[l]);
            }
        }
        dp[r] = leftMax + 1;
    }

    cout << *max_element(dp.begin(), dp.end()) << endl;
    return 0;
}

希望这个专栏能让您熟练掌握算法, 🎁🎁🎁 立即订阅。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏