跳至主要內容

【DP】2024E-书籍叠放

【DP】2024E-书籍叠放

题目描述与示例

本题练习地址：https://www.algomooc.com/problem/P3430

题目描述

书籍的长、宽都是整数对应(l,w)。如果书A的长宽度都比B长宽大时，则允许将B排列放在A上面。

现在有一组书籍，书籍叠放时要求书籍不能做旋转，请计算最多能有多少个书籍能叠放在一起。

输入描述

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

说明：总共4本书籍，

第一本长度为20，宽度为16；

第二本书长度为15宽度为11；

依次类推，最后一本书长度为9，宽度为10

输出描述

输出：3

最多能有多少个规格书籍能叠放在一起

示例一

输入

20,16,15,11,10,10,9,10

输出

3

说明

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

示例二

输入

20,15,15,20

输出

1

解题思路

注意：本题和LC354. 俄罗斯套娃信封问题、 面试题 17.08. 马戏团人塔、LC1626. 无矛盾的最佳球队等题目几乎完全一致，属于LeetCode 300、最长递增子序列的轻变形题目。

如何转变为LIS问题

长度严格不等的情况

先考虑一种比较简单的情况，所有书本的长度两两不等，譬如用例

books = [(1, 1), (3, 2), (2, 4), (4, 3)]

我们可以把所有书本按照长度进行排列，得到

books = [(1, 1), (2, 4), (3, 2), (4, 3)]

对books进行排序后，单看长度的话，后面位置的书本长度一定大于前面位置的书本长度，即一定存在books[i][0] > books[j][0]对于任何i > j成立。故我们只需要考虑宽度即可，把所有宽度从books数组中提取出来可以得到宽度数组widths

widths = [1, 4, 2, 3]

为了使得叠放的书本尽可能多，子序列就要尽可能长。问题实际上转变为对宽度数组widths考虑最长递增子序列LIS问题，即宽度数组能够取得的LIS长度，就是整个书本数组能够取得的LIS长度。故我们对widths数组进行LIS问题的求解即可。

上述例子可以得到widths的LIS是[1, 2, 3]，对应books的LIS是[(1, 1), (3, 2), (4, 3)]，长度3即为答案。

长度可能相等的情况

对于书本长度可能相等的情况呢？考虑用例

books = [(1, 1), (2, 3), (4, 4), (2, 2)]

如果我们考虑对长度进行升序排序后，对长度相等的书本根据宽度也进行升序排序，那么会得到

books = [(1, 1), (2, 2), (2, 3), (4, 4)]

提取宽度数组widths得到

widths = [1, 2, 3, 4]

显然此时widths的LIS是[1, 2, 3, 4]，长度为4，但其对应的books数组的LIS并不能取[(1, 1), (2, 2), (2, 3), (4, 4)]，因为长度同样为2的书本的叠放并不符合要求。

为了避免上述问题，我们考虑对长度进行升序排序后，对长度相等的书本根据宽度进行降序排序，那么会得到

books = [(1, 1), (2, 3), (2, 2), (4, 4)]

提取宽度数组widths得到

widths = [1, 3, 2, 4]

此时widths的LIS是[1, 3, 4]或者[1, 2, 4]，对应的books数组的LIS为[(1, 1), (2, 3), (4, 4)]或者[(1, 1), (2, 2), (4, 4)]，符合要求。

这是因为对于长度相等的书本而言，更小的宽度被排到更后的位置，这样当我们对宽度考虑LIS问题时，就不会出现长度相等的书籍出现在递增子序列中的情况了。

排序依据

故最终我们选择先依据长度升序，再依据宽度降序的方式，对书本数组books进行排序

books.sort(key = lambda item: (item[0], -item[1]))

dp求解LIS问题

在对书本数组进行排序之后，剩下部分就是对所有书本宽度做常规的LIS问题了，此部分可以参考LeetCode 300、最长递增子序列。

我们考虑动态规划三部曲：

  1. dp数组的含义是什么？
  • dp数组是一个长度为n的一维列表，dp[i]表示以第i本书籍为结尾的最长递增子序列的长度
  1. 动态转移方程是什么？
  • 对于第i本书，我们都去考虑其前面的第i-1本书，用索引j表示。如果第i本书的宽度大于第j本书的宽度，即存在books[i][1] > books[j][1]成立，那么i可能可以放在j的后面。
  • 如果选择i放在j的下方能使得i叠放更多书籍，或者说递增子序列能够更长，那么我们选择j。
for i in range(1, n)    
    for j in range(i):
        if books[i][1] > books[j][1]:
            dp[i] = max(dp[j]+1, dp[i])
  1. dp数组如何初始化？
  • 以第0本书为结尾的最长递增子序列的长度为1。其余书本对应的最长递增子序列长度也可以默认为1。
dp = [1] * n

PS：这类LIS问题还存在更加优秀的时间复杂度为O(nlogn)的贪心+二分的解法，但已经有点超纲。对于OD考试而言，时间复杂度为O(n^2)的dp解法已经完全够用。

具体可详见文档再论LIS问题：贪心+二分算法

代码

解法一：DP

Python

# 题目：2024E-书籍叠放
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：DP/LIS问题变种
# 代码看不懂的地方，请直接在群上提问


# 输入
lst = list(map(int, input().split(",")))
# 将输入长度为2n的一维列表转化为n*2的二维列表
# books[i] = (第i本书的长度，第i本书的宽度)
books = [(lst[i], lst[i+1]) for i in range(0, len(lst), 2)]
# 对n本书进行排序，先依照长度升序排序，长度相等时依据宽度降序排序
books.sort(key = lambda item: (item[0], -item[1]))
# 获得书本的数量n
n = len(books)

# 初始化dp数组
# dp[i]选择了第i本书籍为底部书籍，能够叠放的最多数目
# 或者说以第i本书籍为结尾的最长递增子序列的长度
dp = [1] * n

# 遍历每一本书籍i
for i in range(1, n):
    # 考虑书籍i之前的所有书籍j
    for j in range(i):
        # 如果书籍i的宽度大于书籍j的宽度
        # 那么书籍j可以放在书籍i的上方
        # 如果选择i放在j的下方能使得i叠放更多书籍
        # 则选择j
        if books[i][1] > books[j][1]:
            dp[i] = max(dp[j]+1, dp[i])

# dp数组中的最大值为能够叠放的最大书籍数目
print(max(dp))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        String[] arr = input.nextLine().split(",");
        int[] lst = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            lst[i] = Integer.parseInt(arr[i]);
        }

        List<Pair<Integer, Integer>> books = new ArrayList<>();
        for (int i = 0; i < lst.length; i += 2) {
            books.add(new Pair<>(lst[i], lst[i + 1]));
        }

        books.sort((a, b) -> {
            if (a.getKey().equals(b.getKey())) {
                return b.getValue() - a.getValue();
            }
            return a.getKey() - b.getKey();
        });

        int n = books.size();

        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (books.get(i).getValue() > books.get(j).getValue()) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
        }

        int maxStackedBooks = Arrays.stream(dp).max().orElse(0);
        System.out.println(maxStackedBooks);
    }

    static class Pair<K, V> {
        private final K key;
        private final V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }
}

C++

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string line;
    getline(cin, line);
    istringstream iss(line);
    vector<int> lst;
    int num;
    while (iss >> num) {
        lst.push_back(num);
        if (iss.peek() == ',')
            iss.ignore();
    }

    vector<pair<int, int>> books;
    for (int i = 0; i < lst.size(); i += 2) {
        books.push_back(make_pair(lst[i], lst[i + 1]));
    }

    sort(books.begin(), books.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        if (a.first == b.first) {
            return b.second < a.second;
        }
        return a.first < b.first;
    });

    int n = books.size();

    vector<int> dp(n, 1);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (books[i].second > books[j].second) {
                dp[i] = max(dp[j] + 1, dp[i]);
            }
        }
    }

    int maxStackedBooks = *max_element(dp.begin(), dp.end());
    cout << maxStackedBooks << endl;

    return 0;
}

时空复杂度

时间复杂度：O(``N^2``)。dp过程需要进行双重循环，复杂度为O(N^2)。排序的时间复杂度为O(NlogN)。总的复杂度取其中的较大值，为O(N^2)。

空间复杂度：O(``N``)。dp数组所占空间。

解法二：贪心+二分

Python

# 题目：2024E-书籍叠放
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：排序+贪心 +二分/LIS问题变种
# 代码看不懂的地方，请直接在群上提问#


def binarySearch(ans, w):
    # 在ans中找到第一个大于等于w的下标，并把该下标对应的元素修改为较小的值w
    left, right = 0, len(ans)   # 左闭右开搜索区间
    while(left < right):
        mid = (left + right) >> 1
        if ans[mid] >= w:
            right = mid
        else:
            left = mid + 1
    # 修改
    ans[left] = w               
    return


# 输入
lst = list(map(int, input().split(",")))
# 将输入长度为2n的一维列表转化为n*2的二维列表
# books[i] = (第i本书的长度，第i本书的宽度)
books = [(lst[i], lst[i+1]) for i in range(0, len(lst), 2)]
# 对n本书进行排序，先依照长度升序排序，长度相等时依据宽度降序排序
books.sort(key = lambda item: (item[0], -item[1]))
# 获得书本的数量n
n = len(books)
# 初始化答案递增序列，初始化为第一本书的宽度
ans = [books[0][1]]
# 遍历所有书籍，此时所有书籍的长度已经按照长度l来排列
for l, w in books:
    # 如果当前书籍的宽度w超过ans中最后一本书的宽度
    # 则延长ans这个递增序列
    if w > ans[-1]:
        ans.append(w)
    # 否则，找到ans中第一本宽度大于等于w的书籍
    # 将其修改为w
    else:
        binarySearch(ans, w)
        
# 输出ans的长度，即为答案
print(len(ans))

Java

import java.util.*;

public class Main {
    // 在ans中找到第一个大于等于w的下标，并把该下标对应的元素修改为较小的值w
    private static void binarySearch(List<Integer> ans, int w) {
        int left = 0, right = ans.size();
        // 左闭右开搜索区间
        while (left < right) {
            int mid = (left + right) / 2;
            if (ans.get(mid) >= w) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        // 修改
        ans.set(left, w);
    }

    // 计算可以堆叠的书籍的最大高度
    public static int maxStackHeight(List<Integer> lst) {
        List<List<Integer>> books = new ArrayList<>();
        for (int i = 0; i < lst.size(); i += 2) {
            books.add(Arrays.asList(lst.get(i), lst.get(i + 1)));
        }
        // 对n本书进行排序，先依照长度升序排序，长度相等时依据宽度降序排序
        Collections.sort(books, (a, b) -> a.get(0).equals(b.get(0)) ? b.get(1) - a.get(1) : a.get(0) - b.get(0));
        List<Integer> ans = new ArrayList<>();
        ans.add(books.get(0).get(1)); // 初始化答案递增序列，初始化为第一本书的宽度
        // 遍历所有书籍，此时所有书籍的长度已经按照长度l来排列
        for (List<Integer> book : books) {
            int l = book.get(0), w = book.get(1);
            // 如果当前书籍的宽度w超过ans中最后一本书的宽度，则延长ans这个递增序列
            if (w > ans.get(ans.size() - 1)) {
                ans.add(w);
            } else { // 否则，找到ans中第一本宽度大于等于w的书籍，将其修改为w
                binarySearch(ans, w);
            }
        }
        // 返回ans的长度，即为答案
        return ans.size();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        String[] inputs = input.split(",");
        List<Integer> lst = new ArrayList<>();
        for (String str : inputs) {
            lst.add(Integer.parseInt(str));
        }
        System.out.println(maxStackHeight(lst));
        scanner.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;

// 在ans中找到第一个大于等于w的下标，并把该下标对应的元素修改为较小的值w
void binarySearch(vector<int>& ans, int w) {
    int left = 0, right = ans.size();
    // 左闭右开搜索区间
    while (left < right) {
        int mid = (left + right) / 2;
        if (ans[mid] >= w) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    // 修改
    ans[left] = w;
}

// 计算可以堆叠的书籍的最大高度
int maxStackHeight(vector<int>& lst) {
    vector<vector<int>> books;
    for (int i = 0; i < lst.size(); i += 2) {
        books.push_back({lst[i], lst[i + 1]});
    }
    // 对n本书进行排序，先依照长度升序排序，长度相等时依据宽度降序排序
    sort(books.begin(), books.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] == b[0] ? b[1] < a[1] : a[0] < b[0];
    });
    vector<int> ans;
    ans.push_back(books[0][1]); // 初始化答案递增序列，初始化为第一本书的宽度
    // 遍历所有书籍，此时所有书籍的长度已经按照长度l来排列
    for (auto& book : books) {
        int l = book[0], w = book[1];
        // 如果当前书籍的宽度w超过ans中最后一本书的宽度，则延长ans这个递增序列
        if (w > ans.back()) {
            ans.push_back(w);
        } else { // 否则，找到ans中第一本宽度大于等于w的书籍，将其修改为w
            binarySearch(ans, w);
        }
    }
    // 返回ans的长度，即为答案
    return ans.size();
}

int main() {
    string input;
    getline(cin, input);
    stringstream ss(input);
    vector<int> lst;
    int num;
    while (ss >> num) {
        lst.push_back(num);
        if (ss.peek() == ',') ss.ignore();
    }
    cout << maxStackHeight(lst) << endl;
    return 0;
}

时空复杂度

时间复杂度：O(NlogN)。

空间复杂度：O(N)。

本站内容包括机考真题解析、八股文速记、技术&行为面试指南、真实上岸经验与截图墙。
Copyright © 2025 欧弟算法