Chương 39 - Sorting kết hợp Dynamic Programming

Sort + DP là combo mạnh khi thứ tự items quan trọng và DP trên thứ tự đó. Pattern thường gặp: sort theo một thuộc tính, rồi LIS-like DP trên thuộc tính khác.

Mục tiêu chương

Sau chương này, bạn sẽ:

Sort là preprocessing rộng (không phải chỉ DP).
LIS sau khi sort 2D → giảm dimension.
Trick (w asc, h desc) để cùng w không tạo “LIS” giả.
Một số bài thực ra monotonic stack (Visible People) hoặc greedy interval (Min Taps).

Khi nào dùng pattern này?

Đầu vào có cấu trúc nested/dimension và sort giúp ngầm hoá 1 chiều.
LIS-like bài với 2D / weighted.
Job scheduling, envelope stacking, divisible subset.

Bài tự luyện cuối chương

LC 1235 - Maximum Profit in Job Scheduling
LC 1626 - Best Team With No Conflicts

39.1 Largest Divisible Subset (LC 368)

Đề bài

Cho nums (phân biệt). Tìm subset lớn nhất sao cho mọi cặp (a, b) trong đó a % b == 0 hoặc b % a == 0.

Ví dụ

Input:  nums = [1, 2, 4, 8]
Output: [1, 2, 4, 8]   (subset lớn nhất mà mọi cặp (a, b) đều có a % b == 0 hoặc b % a == 0)

Ràng buộc

1 <= len(nums) <= 1000
1 <= nums[i] <= 2·10^9

Clarifying questions

nums có 1 phần tử? → Trả [nums[0]].

Hướng tiếp cận

Sort tăng dần. dp[i] = subset lớn nhất kết thúc tại nums[i].

dp[i] = max(dp[j] + 1 for j < i if nums[i] % nums[j] == 0).

Track parent[] để reconstruct subset.

Code Python 3

from typing import List

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)
        dp = [1] * n
        parent = [-1] * n
        best_idx = 0
        for i in range(n):
            for j in range(i):
                if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    parent[i] = j
            if dp[i] > dp[best_idx]:
                best_idx = i
        result = []
        while best_idx != -1:
            result.append(nums[best_idx])
            best_idx = parent[best_idx]
        return result[::-1]

Phân tích độ phức tạp

Thời gian: O(n²) DP + O(n log n) sort.
Bộ nhớ: O(n).

Bình luận

Bẫy: cần sort trước để pattern divisibility áp được.
Follow-up: LC 354 (Russian Doll Envelopes) cùng sort + LIS.

Bài tự luyện liên quan

LC 354 - Russian Doll Envelopes (bài 39.2)
LC 1691 - Stacking Cuboids (bài 39.3)

39.2 Russian Doll Envelopes (LC 354) - recap

Đã giải đầy đủ ở Chương 29.6. Sort 2D + LIS với binary search.

Liên hệ với chương này

Pattern “sort 2D + LIS theo chiều còn lại” tái xuất ở bài 39.3 (Stacking Cuboids, 3D), 39.5 (Visible People), 45.x (Sorting + DP nâng cao).

Code Python 3 (recap)

from bisect import bisect_left
from typing import List

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        envelopes.sort(key=lambda e: (e[0], -e[1]))
        tails: list[int] = []
        for _, h in envelopes:
            i = bisect_left(tails, h)
            if i == len(tails):
                tails.append(h)
            else:
                tails[i] = h
        return len(tails)

Phân tích độ phức tạp

Thời gian: O(n log n). Bộ nhớ: O(n).

Bài tự luyện liên quan

LC 300 - LIS
LC 1691 - Stacking Cuboids (bài 39.3)

39.3 Maximum Height by Stacking Cuboids (LC 1691)

Đề bài

Cho cuboids[i] = [w, l, h]. Có thể rotate mỗi cuboid (chọn 1 trong 3 chiều làm height). Stack i lên j nếu mọi chiều i ≤ chiều j. Tìm height max.

Ví dụ

Input:  cuboids = [[50,45,20], [95,37,53], [45,23,12]]
        (mỗi cuboid [w, l, h]; có thể xoay; stack được nếu w1≤w2, l1≤l2, h1≤h2)
Output: 190   (chiều cao stack lớn nhất)

Ràng buộc

1 <= len(cuboids) <= 100

Clarifying questions

Không thể stack? → Trả max(c[2] for c in cuboids).

Hướng tiếp cận

Insight: sort 3 chiều mỗi cuboid → cuboid khác stack được lên nhau ↔︎ 3 chiều sorted của cái dưới ≥ 3 chiều sorted của cái trên (sau khi sort all cuboids tăng).

Sau khi sort, bài thành LIS 3D.

Code Python 3

from typing import List

class Solution:
    def maxHeight(self, cuboids: List[List[int]]) -> int:
        for c in cuboids:
            c.sort()
        cuboids.sort()
        n = len(cuboids)
        dp = [c[2] for c in cuboids]
        for i in range(n):
            for j in range(i):
                if all(cuboids[j][k] <= cuboids[i][k] for k in range(3)):
                    dp[i] = max(dp[i], dp[j] + cuboids[i][2])
        return max(dp)

Phân tích độ phức tạp

Thời gian: O(n²) DP + O(n log n) sort.
Bộ nhớ: O(n).

Bình luận

Bẫy: không sort 3 chiều của cuboid trước → kết quả sai.
Follow-up: LC 354 (Russian Doll) đơn giản hơn (2D).

Bài tự luyện liên quan

LC 354 - Russian Doll Envelopes (bài 39.2)
LC 300 - LIS

39.4 Maximum Profit in Job Scheduling (LC 1235)

Đề bài

Cho jobs = [(start, end, profit)]. Chọn các job không overlap, max tổng profit.

Ví dụ

Input:  startTime=[1,2,3,3], endTime=[3,4,5,6], profit=[50,10,40,70]
Output: 120

Ràng buộc

1 <= len(jobs) <= 5·10^4
1 <= startTime[i] < endTime[i] <= 10^9

Clarifying questions

Không có job? → Trả 0.
Profit có thể âm? → Theo đề: profit ≥ 1.

Hướng tiếp cận

Sort theo end. dp[i] = max profit dùng các job [0..i].

dp[i] = max(dp[i-1], dp[k] + jobs[i].profit) với k = job cuối có end <= jobs[i].start.

Binary search tìm k → O(n log n).

Code Python 3

from bisect import bisect_right
from typing import List

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        jobs = sorted(zip(endTime, startTime, profit))
        ends = [j[0] for j in jobs]
        dp = [0] * (len(jobs) + 1)
        for i, (end, start, p) in enumerate(jobs):
            k = bisect_right(ends, start)
            dp[i + 1] = max(dp[i], dp[k] + p)
        return dp[-1]

Phân tích độ phức tạp

Thời gian: O(n log n).
Bộ nhớ: O(n).

Bình luận

Pattern “sort by end + binary search prev” quan trọng - gặp ở weighted interval scheduling.

Bài tự luyện liên quan

LC 300 - LIS
LC 1751 - Maximum Number of Events That Can Be Attended II

39.5 Number of Visible People in a Queue (LC 1944)

Đề bài

Cho heights. Mỗi người thấy được người sau họ trong queue đến khi gặp người cao hơn họ hoặc cao hơn cả người vừa thấy. Đếm số người mỗi người thấy.

Ví dụ

Input:  heights = [10, 6, 8, 5, 11, 9]
        (heights[i] = chiều cao người thứ i trong queue, mọi heights[i] khác nhau)
Output: [3, 1, 2, 1, 1, 0]
        (answer[i] = số người ở bên phải mà người thứ i nhìn thấy)

Ràng buộc

n == len(heights)
1 <= n <= 10^5

Clarifying questions

Tất cả cùng chiều cao? → Mỗi người chỉ thấy người ngay sau.

Hướng tiếp cận

Monotonic stack từ phải sang trái. Mỗi người: pop hết người thấp hơn từ stack (đếm vào kết quả), cộng 1 nếu stack còn (người cao hơn).

Code Python 3

from typing import List

class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        n = len(heights)
        result = [0] * n
        stack: list[int] = []
        for i in range(n - 1, -1, -1):
            while stack and heights[i] > stack[-1]:
                stack.pop()
                result[i] += 1
            if stack:
                result[i] += 1
            stack.append(heights[i])
        return result

Phân tích độ phức tạp

Thời gian: O(n).
Bộ nhớ: O(n).

Bình luận

Pattern monotonic stack áp dụng cho bài Sort + DP (count-based).

Bài tự luyện liên quan

LC 901 - Online Stock Span
LC 84 - Largest Rectangle in Histogram

39.6 Minimum Number of Taps to Open to Water a Garden (LC 1326)

Đề bài

Garden độ dài n. Tap i ở vị trí i tưới [i - r, i + r]. Min tap để tưới hết.

Ví dụ

Input:  n=5, ranges=[3,4,1,1,0,0]
Output: 1

Ràng buộc

1 <= n <= 10^4
ranges.length == n+1

Clarifying questions

Không có tap nào tưới (0,0)? → Trả -1.

Hướng tiếp cận

Chuyển sang Jump Game II (16.2): cho mỗi vị trí i, farthest[i] = vị trí xa nhất tới được nếu bắt đầu ở i. Greedy.

Code Python 3

from typing import List

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        farthest = [0] * (n + 1)
        for i, r in enumerate(ranges):
            left = max(0, i - r)
            right = min(n, i + r)
            farthest[left] = max(farthest[left], right)
        taps = 0
        current_end = 0
        next_end = 0
        for i in range(n + 1):
            if i > next_end:
                return -1
            if i > current_end:
                taps += 1
                current_end = next_end
            next_end = max(next_end, farthest[i])
        return taps

Phân tích độ phức tạp

Thời gian: O(n + max_range).
Bộ nhớ: O(n + max_range).

Bình luận

Bẫy: dùng cùng pattern Jump Game II (Chương 16.2) - convert range → max reach.
Follow-up: LC 1024 (Video Stitching) tương tự.

Bài tự luyện liên quan

LC 45 - Jump Game II (Chương 16.2)
LC 55 - Jump Game (Chương 16.1)

Tóm tắt chương & Quyết định

“Sort as preprocessing” - phạm vi rộng hơn DP

Chương này tập hợp các bài mà bước đầu tiên là sort, sau đó áp dụng: - DP (Russian Doll, Job Scheduling). - Monotonic stack (LC 1944 Visible People - đứng riêng nhưng phụ thuộc thứ tự). - Greedy interval (LC 1326 Minimum Taps).

Nhãn chương rộng hơn “Sort + DP” cứng nhắc; coi như “Sort preprocessing patterns”.

Russian Doll Envelopes (LC 354) - lens phân biệt

Chương 4: dùng 2D sort để minh hoạ “sort theo nhiều khoá”.
Chương 39 (đây): xem như LIS sau sort = bridge giữa sort và DP.

Job Scheduling (LC 1235) - timeline + previous-compatible

jobs sorted by endTime: J1=[1,3,50], J2=[2,4,10], J3=[3,5,40], J4=[3,6,70]
                                ↑           ↑           ↑
                              end=3        end=4       end=5,6

dp[i] = max(dp[i-1], jobs[i].profit + dp[prev(i)])
prev(i) = job cuối cùng có endTime ≤ jobs[i].startTime  ← binary search!

Visible People In Queue (LC 1944) - monotonic stack

Sort không thực sự là sort; người ta đứng trong queue đã có vị trí cố định.
Monotonic stack từ phải sang: phần tử trong stack là “người cao nhất nhìn thấy được”.
Đặt ở chương này nếu coi “sort theo position” làm bước tiền xử lý ngầm. Có thể tách ra chương 18 trong lần re-edit sau.

Minimum Taps (LC 1326) - greedy interval

Convert mỗi tap (i, range) thành interval [i - r, i + r].
Sau khi sort, dùng “jump game” / “min number of intervals to cover” (greedy).
Không phải DP, nhưng đại diện cho lớp bài “sort + interval cover”.