Chương 38 - Binary Search kết hợp Dynamic Programming

Khi DP transition cần “tìm nhanh giá trị tối ưu trong subset đã xét”, binary search vào prefix optimal có thể giảm O(n²) xuống O(n log n). Pattern này gặp ở LIS, Russian Doll Envelopes, Constrained Subsequence Sum.

Mục tiêu chương

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

  • Pattern: DP transition cần “tìm best previous” → dùng binary search.
  • LIS O(n log n) với bisect trên tails.
  • LIS II với segment tree khi cần range max query.
  • Job Scheduling: binary search vị trí job không overlap.

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

  • DP có “tìm vị trí” trong cấu trúc đã sort.
  • dp[i] = max/min(...) mà argmax có thể tìm bằng binary search.

Template code 

from bisect import bisect_left, bisect_right

# DP với binary search lookup
tails = []
for x in arr:
    idx = bisect_left(tails, x)
    if idx == len(tails):
        tails.append(x)
    else:
        tails[idx] = x

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

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

38.1 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

Đây là gateway cho pattern BS + DP: sau sort 2D, transition của LIS (tails[bisect_left(tails, x)] = x) chính là binary search trên cấu trúc DP.

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 (Chương 39).

38.2 Longest Increasing Subsequence II (LC 2407)

Đề bài

LIS với constraint: nums[i+1] - nums[i] <= k. Tìm độ dài max.

Ví dụ 

Input:  nums=[4,2,1,4,3,4,5,8,15], k=3
Output: 5

Ràng buộc

  • 1 <= len(nums) <= 10^5
  • 1 <= nums[i], k <= 10^5

Clarifying questions

  • k = 0? → Strict LIS (<).
  • k âm? → Theo đề: k ≥ 1.

Hướng tiếp cận

Segment Tree với max query (range max trên dp values).

dp[v] = max LIS kết thúc với value v. Transition: dp[v] = max(dp[v-k..v-1]) + 1.

Segment tree cho phép range max query O(log V) per step. Total O(n log V).

Code Python 3 

from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        n = max(nums)
        size = 1
        while size < n + 1: size <<= 1
        tree = [0] * (2 * size)

        def update(i: int, val: int):
            i += size
            tree[i] = max(tree[i], val)
            while i > 1:
                i //= 2
                tree[i] = max(tree[2*i], tree[2*i+1])

        def query(l: int, r: int) -> int:
            res = 0
            l += size; r += size + 1
            while l < r:
                if l & 1: res = max(res, tree[l]); l += 1
                if r & 1: r -= 1; res = max(res, tree[r])
                l //= 2; r //= 2
            return res

        best = 0
        for x in nums:
            lo = max(1, x - k)
            cur = query(lo, x - 1) + 1
            update(x, cur)
            best = max(best, cur)
        return best

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

  • Thời gian: O(n log V) với V = max value.
  • Bộ nhớ: O(V) cho segment tree.

Bình luận

  • Bẫy: segment tree index - coordinate compression cần thiết khi V lớn.
  • Follow-up: LC 300 (LIS đơn giản) - Chương 29.2.

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

  • LC 300 - LIS (Chương 29.2)
  • LC 673 - Number of LIS (bài 38.3)

38.3 Number of Longest Increasing Subsequence (LC 673)

Đề bài

Đếm số LIS có độ dài max của nums.

Ví dụ 

Input:  nums = [1, 3, 5, 4, 7]
Output: 2   (số LIS độ dài tối đa: [1,3,5,7] và [1,3,4,7])

Ràng buộc

  • 1 <= len(nums) <= 2000
  • -10^6 <= nums[i] <= 10^6

Clarifying questions

  • Tất cả số bằng nhau? → Có n LIS độ dài 1.
  • Mảng rỗng? → Trả 0.

Hướng tiếp cận

DP O(n²): dp[i] = (length, count) - length của LIS kết thúc tại i, count của số LIS đó.

Có version O(n log n) với segment tree.

Code Python 3 

from typing import List

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        length = [1] * n
        count = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if length[j] + 1 > length[i]:
                        length[i] = length[j] + 1
                        count[i] = count[j]
                    elif length[j] + 1 == length[i]:
                        count[i] += count[j]
        max_len = max(length)
        return sum(c for l, c in zip(length, count) if l == max_len)

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

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

Bình luận

  • Bẫy: track cả length và count → dp[i] = (len, cnt).
  • Follow-up: LC 300 (chỉ length).

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

  • LC 300 - LIS (Chương 29.2)
  • LC 354 - Russian Doll Envelopes (bài 38.1)

38.4 Max Sum of Rectangle No Larger Than K (LC 363)

Đề bài

Ma trận. Tìm submatrix có tổng max ≤ k.

Ví dụ 

Input:  matrix=[[1,0,1],[0,-2,3]], k=2
Output: 2

Ràng buộc

  • 1 <= m, n <= 100
  • -100 <= matrix[i][j] <= 100

Clarifying questions

  • Matrix âm? → Có thể; submatrix sum cũng âm.
  • k âm? → Có thể.

Hướng tiếp cận

Fix 2 cột (c1, c2). Tổng mỗi row trong khoảng → 1D array. Tìm subarray tổng gần k nhất ≤ k: **prefix sum + SortedList

  • binary search**.

Code Python 3 

from sortedcontainers import SortedList
from typing import List

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        rows, cols = len(matrix), len(matrix[0])
        result = -float('inf')
        for c1 in range(cols):
            row_sums = [0] * rows
            for c2 in range(c1, cols):
                for r in range(rows):
                    row_sums[r] += matrix[r][c2]
                # Tìm subarray sum lớn nhất ≤ k.
                sl = SortedList([0])
                prefix = 0
                for v in row_sums:
                    prefix += v
                    # Tìm prefix' ≥ prefix - k → subarray sum = prefix - prefix' ≤ k.
                    idx = sl.bisect_left(prefix - k)
                    if idx < len(sl):
                        result = max(result, prefix - sl[idx])
                    sl.add(prefix)
        return result

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

  • Thời gian: O(rows · cols² · log).
  • Bộ nhớ: O(cols).

Bình luận

  • Bẫy: dùng SortedList (cần pip install sortedcontainers) - không có sẵn trong Python stdlib.
  • Follow-up: LC 1074 - counting submatrix với hash.

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

  • LC 1074 - Number of Submatrices That Sum to Target
  • LC 363 - Max Sum Rectangle (bài này)

38.5 Constrained Subsequence Sum (LC 1425)

Đề bài

Cho nums và k. Tìm max sum của subsequence sao cho mọi cặp index liên tiếp trong subsequence cách nhau ≤ k.

Ví dụ 

Input:  nums=[10,2,-10,5,20], k=2
Output: 37

Ràng buộc

  • 1 <= k <= len(nums) <= 10^5
  • -10^4 <= nums[i] <= 10^4

Clarifying questions

  • k ≥ n? → Tương đương Maximum Subarray (Kadane).
  • All negative? → Trả max(nums) (chọn 1 element).

Hướng tiếp cận

DP dp[i] = nums[i] + max(0, max(dp[i-k..i-1])).

max(dp[i-k..i-1]) qua sliding window max (Chương 18.4) → O(n).

Code Python 3 

from collections import deque
from typing import List

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [0] * n
        dq: deque[int] = deque()
        best = -float('inf')
        for i in range(n):
            window_max = dp[dq[0]] if dq else 0
            dp[i] = nums[i] + max(0, window_max)
            best = max(best, dp[i])
            while dq and dp[dq[-1]] <= dp[i]:
                dq.pop()
            dq.append(i)
            if dq[0] == i - k:
                dq.popleft()
        return best

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

  • Thời gian: O(n).
  • Bộ nhớ: O(n) cho deque + dp.

Bình luận

  • Bẫy: quên max(0, ...) → dp âm có thể bị chọn nhầm.
  • Follow-up: LC 239 (Sliding Window Max) cùng deque pattern.

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

  • LC 239 - Sliding Window Maximum (Chương 18.4)
  • LC 1696 - Jump Game VI

38.6 Allocate Mailboxes (LC 1478)

Đề bài

Cho houses (vị trí). Đặt k mailbox sao cho tổng distance(house → nearest mailbox) min.

Ví dụ 

Input:  houses=[1,4,8,10,20], k=3
Output: 5

Ràng buộc

  • 1 <= k <= len(houses) <= 100
  • 1 <= houses[i] <= 10^4

Clarifying questions

  • k = n? → Mỗi nhà 1 mailbox → cost = 0.

Hướng tiếp cận

DP: dp[i][j] = min cost dùng j mailbox cho houses[:i].

Transition: dp[i][j] = min(dp[p][j-1] + cost(houses[p:i])) với cost là tổng distance khi đặt 1 mailbox cho range - = sum |x - median|.

O(k · n²). Có thể tăng tốc bằng divide-conquer DP optimization → O(k · n log n).

Code Python 3 

from typing import List

class Solution:
    def minDistance(self, houses: List[int], k: int) -> int:
        houses.sort()
        n = len(houses)
        # cost[l][r] = chi phí đặt 1 mailbox cho houses[l..r]
        cost = [[0] * n for _ in range(n)]
        for l in range(n):
            for r in range(l + 1, n):
                mid = houses[(l + r) // 2]
                cost[l][r] = sum(abs(houses[i] - mid) for i in range(l, r + 1))

        INF = float('inf')
        dp = [[INF] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 0
        for i in range(1, n + 1):
            for j in range(1, k + 1):
                for p in range(j - 1, i):
                    dp[i][j] = min(dp[i][j], dp[p][j - 1] + cost[p][i - 1])
        return dp[n][k]

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

  • Thời gian: O(k · n² + n³) (precompute cost + DP).
  • Bộ nhớ: O(k · n + n²).

Bình luận

  • Median minimizes sum |x - m| - tinh tế của bài.

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

  • LC 1959 - Minimum Total Space Wasted With K Resizing Operations
  • LC 410 - Split Array Largest Sum (Chương 25.3)

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

“BS as a lookup inside DP/Optimization”

  • Đôi khi DP có transition cần tìm “vị trí phù hợp nhất” trong tail của state - đây là chỗ binary search vào.
  • Đôi khi transition cần range max/min query → segment tree hoặc balanced BST. Vẫn xếp vào chương này vì cùng họ “tra cứu nhanh bên trong DP”.

LIS II (LC 300) - không hẳn là binary search

  • Patience sorting với array tails: dùng bisect_left để tìm vị trí thay = binary search.
  • LC 354 (Russian Doll Envelopes): sort (w asc, h desc) rồi LIS trên h = patience.
  • LC 1187 (Make Array Strictly Increasing): DP + sorted lookup, không thuần LIS.

Range max query - Segment Tree

LC 2407 (Longest Increasing Subsequence II): không thể dùng patience đơn giản vì có ràng buộc gap ≤ k ⇒ cần segment tree lookup dp[v - k .. v - 1].

Max Sum Rectangle ≤ K (LC 363)

  • Fix 2 cột → bài thành max subarray sum ≤ k trên array tổng theo hàng.
  • Dùng SortedList + bisect để tìm prefix - target gần nhất ≤ k ⇒ không phải DP thuần, nhưng dùng cùng family “binary search vào structure đã sắp”.

Allocate Mailboxes (LC 1478) - median cost precompute

  • Với 1 đoạn [l..r], cost tối ưu = tổng khoảng cách đến median ⇒ precompute cost[l][r].
  • DP dp[k][i] = chia houses[..i] thành k cluster.
  • Transition: dp[k][i] = min_{j} dp[k-1][j] + cost[j+1][i].