Quy hoạch động một chiều trên dãy

Minh sắp xếp 5 gian hàng có phần thưởng lần lượt là 4, 8, 5, 3 và 9 điểm. Bạn chỉ được chọn các gian không kề nhau. Chọn gian có điểm cao nhất trước chưa chắc cho tổng cao nhất. Làm sao xét hết các lựa chọn mà không thử mọi tập hợp?

Một chỉ số có thể mô tả nhiều câu hỏi khác nhau

Quy hoạch động một chiều (one-dimensional dynamic programming) lưu kết quả của các bài toán con theo một chỉ số. Bài 28 giới thiệu ý tưởng lưu kết quả để tránh tính lại. Ở đây ta tập trung vào việc chọn ý nghĩa cho chỉ số ấy.

Trong bài gian hàng, dp[i] có thể là điểm lớn nhất lấy từ i gian đầu tiên. Đây là trạng thái tiền tố (prefix state). Bạn có thể bỏ qua gian cuối; vì thế kết quả không bắt buộc chứa gian thứ i.

Ở bài khác, dp[i] có thể là điểm tốt nhất của một phương án bắt buộc kết thúc tại vị trí i. Đó là trạng thái kết thúc (ending-at state). Hai cách định nghĩa trông giống nhau nhưng trả lời hai câu hỏi khác nhau.

Một trạng thái cần ghi rõ đơn vị, miền lựa chọn và các điều kiện bắt buộc. Sau đó xác định trạng thái gốc (base case), tức kết quả nhỏ nhất có thể biết trực tiếp. Cuối cùng xét các cách hợp lệ để đi đến trạng thái mới.

Chọn gian không kề nhau bằng trạng thái tiền tố

Đánh số gian từ 1; danh sách Python vẫn bắt đầu từ 0. Đặt dp[i] là điểm lớn nhất từ i gian đầu. Được phép không chọn gian nào, nên dp[0] = 0.

Với gian i, mọi phương án hợp lệ thuộc đúng một trong hai nhóm. Nếu bỏ gian đó, điểm tốt nhất là dp[i-1]. Nếu chọn nó, phải bỏ gian i-1, nên điểm tốt nhất là dp[i-2] + a[i-1]. Lấy giá trị lớn hơn trong hai nhóm. Riêng i = 1, phần trước gian đầu có điểm 0.

Bảng cho thấy gian điểm 8 có thể bị bỏ để chọn hai gian điểm 4 và 5. Khi xét gian cuối, điểm 9 được cộng với kết quả tốt nhất của ba gian đầu. Ta không cộng với dp[4] vì phương án đó có thể chứa gian kề.

def best_gifts(a):
    dp = [0] * (len(a) + 1)
    for i in range(1, len(a) + 1):
        take = a[i - 1] + (dp[i - 2] if i >= 2 else 0)
        dp[i] = max(dp[i - 1], take)
    return dp[-1]

print(best_gifts([4, 8, 5, 3, 9]))
print(best_gifts([]))
print(best_gifts([-3, -1]))

18
0
0

Hai nhóm đã phủ hết khả năng và không vi phạm điều kiện. Nếu một phương án trong nhóm chọn gian cuối có phần trước không tối ưu, thay nó bằng dp[i-2] sẽ không làm phương án xấu đi. Vì vậy công thức đúng từng bước từ trạng thái gốc.

Để thấy vì sao tham lam có thể thất bại, xét năm gian [4, 8, 5, 3, 9]. Chọn gian 9 trước, rồi chọn gian lớn nhất còn hợp lệ là 8, cho tổng 17. Ba gian 4, 5, 9 lại cho tổng 18. Quyết định tại một gian phải tính cả phần đã chọn trước đó, không chỉ so điểm riêng của gian hiện tại.

Khi thiết kế trạng thái, bạn cũng cần biết câu hỏi yêu cầu điểm hay danh sách gian. Bảng trên chỉ giữ điểm tối đa. Nếu hai nhánh bằng nhau, cả hai đều có thể dẫn đến một phương án tối ưu. Muốn in một phương án, bạn có thể đi ngược từ cuối bảng và kiểm tra nhánh nào tạo ra giá trị hiện tại. Lúc chọn gian i, bước lùi là hai vị trí; lúc bỏ nó, bước lùi là một vị trí.

Với 100 000 gian, mỗi gian cần một phép so sánh hai lựa chọn, tức O(n) thời gian. Bảng chiếm O(n) bộ nhớ. Kết quả 0 với dãy toàn âm phụ thuộc vào quy ước được bỏ hết. Nếu đề buộc chọn ít nhất một gian, cần trạng thái và giá trị khởi tạo khác.

Hai biến đủ khi chỉ cần hai trạng thái trước

Khi chỉ cần điểm cuối cùng, công thức gian hàng chỉ đọc dp[i-1] và dp[i-2]. Ta giữ hai số ấy thay cho cả bảng. Cập nhật đồng thời để giá trị mới không ghi đè giá trị cũ quá sớm.

def best_gifts_compact(a):
    prev2 = prev1 = 0
    for x in a:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

print(best_gifts_compact([4, 8, 5, 3, 9]))
print(best_gifts_compact([7]))

18
7

Trước mỗi vòng, prev1 là đáp án của tiền tố đã xét và prev2 là đáp án của tiền tố ngắn hơn một gian. Phép gán đồng thời tính vế phải trước khi cập nhật. Nhờ đó ý nghĩa hai biến vẫn đúng ở vòng tiếp theo.

Thời gian vẫn là O(n), còn bộ nhớ phụ giảm xuống O(1) nếu không tính danh sách đầu vào. Nếu đề yêu cầu in các gian được chọn, cần giữ thêm thông tin để truy vết. Tiết kiệm bộ nhớ không miễn phí nếu sau đó bạn cần khôi phục phương án.

Trong bài gian hàng, ta cũng có thể đọc dữ liệu theo định dạng của máy chấm. Ví dụ sau nhận số gian và một dòng điểm, sau đó áp dụng công thức tiền tố.

4
5 1 1 5

n = int(input())
a = list(map(int, input().split()))
prev2 = prev1 = 0
for x in a[:n]:
    prev2, prev1 = prev1, max(prev1, prev2 + x)
print(prev1)

10

Chọn hai gian ở hai đầu cho điểm tốt nhất. Mỗi vòng vẫn xét đủ hai lựa chọn, nên kết quả không phụ thuộc vào cách đọc danh sách.

Chi phí đến một vị trí dựa vào bước nhảy cuối

Một con ếch đứng tại đá 0. Độ cao bốn viên đá là 10, 30, 40 và 20. Mỗi lần ếch nhảy một hoặc hai vị trí. Chi phí một lần nhảy là hiệu tuyệt đối của hai độ cao.

Đặt dp[i] là chi phí nhỏ nhất để tới đúng đá i. Ta có dp[0] = 0. Bước cuối tới i chỉ có thể xuất phát từ i-1 hoặc i-2, nếu vị trí đó tồn tại. Cộng chi phí bước cuối vào kết quả tốt nhất của từng nơi xuất phát, rồi lấy nhỏ nhất.

h = [10, 30, 40, 20]
dp = [0] * len(h)
for i in range(1, len(h)):
    dp[i] = dp[i - 1] + abs(h[i] - h[i - 1])
    if i >= 2:
        dp[i] = min(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]))
print("độ cao:", *h)
print("chi phí:", *dp)
print("đích:", dp[-1])

độ cao: 10 30 40 20
chi phí: 0 20 30 30
đích: 30

Khi tới đá 3, nhảy từ đá 1 tốn thêm 10; nhảy từ đá 2 tốn thêm 20. Chương trình chọn phương án có tổng nhỏ hơn. Vì mọi đường đi đều có một trong hai bước cuối đó, ta không bỏ sót đường tối ưu.

Nếu có n = 100 000 đá, ta xét tối đa hai bước trước cho mỗi đá. Thời gian là O(n), bộ nhớ bảng là O(n). Nếu được nhảy tối đa k đá, xét mọi bước cuối tốn O(nk); với n = 5000, k = 100, đó là tối đa khoảng 500 000 phép xét.

Dãy con tăng cần nhớ nơi kết thúc

Một dãy con (subsequence) giữ thứ tự các phần tử được chọn, nhưng các phần tử không cần đứng cạnh nhau. Với [3, 1, 4, 2, 5], có thể chọn [1, 2, 5]. Yêu cầu tăng nghiêm ngặt nghĩa là mỗi phần tử sau lớn hơn phần tử trước.

Đặt dp[i] là độ dài dãy con tăng dài nhất kết thúc đúng tại i. Riêng a[i] tạo dãy độ dài 1. Với mỗi j < i có a[j] < a[i], ta nối a[i] sau một dãy tốt nhất kết thúc tại j. Chọn độ dài lớn nhất trong các khả năng đó.

Mọi dãy tăng kết thúc tại i hoặc chỉ gồm a[i], hoặc có một phần tử trước cuối ở vị trí j. Điều kiện a[j] < a[i] là cần và đủ để nối. Xét mọi j vì vị trí ngay trước không nhất thiết thuộc dãy tốt nhất.

Chẳng hạn ở vị trí chứa 5 trong bảng, cả 3, 1, 4 và 2 đều có thể đứng trước. Nhưng mỗi vị trí mang độ dài tốt nhất khác nhau. Không chỉ chọn giá trị nhỏ nhất, ta cần chọn tiền nhiệm có dp[j] lớn nhất trong những vị trí hợp lệ. Nếu có hai tiền nhiệm đạt cùng độ dài, chọn một trong hai vẫn cho cùng độ dài kết quả.

Để khôi phục một dãy, tạo thêm parent[i] ban đầu bằng -1. Khi một j cải thiện dp[i], lưu parent[i] = j. Sau khi tìm vị trí có dp lớn nhất, lần theo các vị trí cha cho đến -1, rồi đảo thứ tự các giá trị. Mảng cha tốn thêm O(n) bộ nhớ. Khi chỉ cần độ dài, không cần mảng này.

def lis(a):
    dp = [1] * len(a)
    for i in range(len(a)):
        for j in range(i):
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)

print(lis([1, 2, 3, 0]))
print(lis([2, 2, 2]))
print(lis([]))

3
1
0

Đáp án là max(dp), không nhất thiết là dp[-1]. Dấu < loại hai giá trị bằng nhau khỏi cùng một dãy tăng nghiêm ngặt. Với 2000 phần tử, số cặp j < i là 1 999 000. Thuật toán tốn O(n²) thời gian và O(n) bộ nhớ; giới hạn lớn hơn có thể cần kỹ thuật khác.

Phần tử cuối nhỏ nhất giúp tìm dãy tăng nhanh hơn

Khi chỉ cần độ dài, ta lưu tails[length - 1] là phần tử cuối nhỏ nhất của một dãy tăng độ dài length đã gặp. Cùng độ dài, phần tử cuối nhỏ hơn tạo cơ hội nối thêm ít nhất như phần tử cuối lớn hơn. Các phần tử trong tails không nhất thiết thuộc cùng một dãy con.

Mảng tails tăng nghiêm ngặt. Thật vậy, bỏ phần tử cuối của một dãy tăng độ dài length + 1 tạo ra một dãy độ dài length có phần tử cuối nhỏ hơn. Vì tails[length - 1] không lớn hơn phần tử cuối đó, nó nhỏ hơn tails[length].

Với mỗi x, tìm vị trí đầu tiên trong tails có giá trị lớn hơn hoặc bằng x bằng bisect_left (xem Bài 13). Thay phần tử ở vị trí ấy bằng x; nếu không có vị trí như vậy, thêm x vào cuối. Các độ dài khác giữ nguyên giá trị cuối nhỏ nhất: x không thể cải thiện độ dài ngắn hơn, và không đủ lớn để nối vào độ dài dài hơn.

from bisect import bisect_left

tails = []
for x in [3, 1, 4, 2, 5, 5]:
    i = bisect_left(tails, x)
    if i == len(tails):
        tails.append(x)
    else:
        tails[i] = x
    print(x, tails)
print("độ dài:", len(tails))

3 [3]
1 [1]
4 [1, 4]
2 [1, 2]
5 [1, 2, 5]
5 [1, 2, 5]
độ dài: 3

Vị trí tìm được bằng số độ dài có phần tử cuối nhỏ hơn x, nên chỉ khi vị trí bằng độ dài hiện tại ta tạo được dãy dài hơn. Dùng bisect_left để hai giá trị bằng nhau không kéo dài dãy tăng nghiêm ngặt. Với 200 000 phần tử, tìm kiếm mỗi lần mất O(log n), tổng là O(n log n) và bộ nhớ là O(n).

Tích đoạn lớn nhất cần giữ cả hai cực trị

Một đoạn con (subarray) gồm các phần tử liên tiếp, khác với dãy con. Với tích, số âm có thể biến tích nhỏ nhất thành tích lớn nhất. Vì vậy chỉ giữ tích lớn nhất kết thúc ở vị trí trước là chưa đủ.

Đặt hi và lo lần lượt là tích lớn nhất và nhỏ nhất của đoạn không rỗng kết thúc tại vị trí hiện tại. Khi gặp x, đoạn mới hoặc chỉ có x, hoặc nối x vào một đoạn trước. Tích lớn nhất và nhỏ nhất mới nằm trong ba giá trị x, hi*x, lo*x.

a = [-2, 3, -4, 0, -1]
hi = lo = answer = a[0]
for x in a[1:]:
    candidates = (x, hi * x, lo * x)
    hi, lo = max(candidates), min(candidates)
    answer = max(answer, hi)
    print(x, hi, lo, answer)

3 3 -6 3
-4 24 -12 24
0 0 0 24
-1 0 -1 24

Cả hai cực trị mới phải dùng hi và lo cũ. Số 0 cho phép đoạn mới bắt đầu lại. Khởi tạo từ phần tử đầu để đoạn bắt buộc không rỗng; khởi tạo đáp án bằng 0 sẽ sai với một phần tử âm.

Mỗi vị trí xét ba giá trị, nên có O(n) phép nhân và O(1) biến phụ. Tuy nhiên số nguyên Python có độ dài không cố định. Khi tích có nhiều chữ số, chi phí nhân và in còn phụ thuộc số chữ số; không thể mặc định mỗi phép nhân là hằng số với đầu vào tùy ý.

Đếm cách giải mã theo độ dài tiền tố

Mỗi số từ 1 đến 26 biểu diễn một chữ cái. Chuỗi 226 có thể chia theo các nhóm 2|2|6, 22|6 hoặc 2|26. Số 0 không biểu diễn một chữ cái riêng, nhưng 10 và 20 hợp lệ.

Đặt dp[i] là số cách giải mã đúng i chữ số đầu. Có một cách xử lý tiền tố rỗng: chưa chọn nhóm nào, nên dp[0] = 1. Nếu chữ số cuối khác 0, nối nó vào mỗi cách của dp[i-1]. Nếu hai chữ số cuối tạo số từ 10 đến 26, nối cả cặp vào mỗi cách của dp[i-2].

Hai nhóm khác nhau ở độ dài nhóm cuối, nên không đếm trùng. Chúng phủ mọi cách hợp lệ vì một chữ cái chỉ mang một hoặc hai chữ số. Nếu một tiền tố không giải mã được, giá trị của nó là 0 và không sinh thêm cách từ nhánh tương ứng.

Chuỗi có số 0 đầu cần giữ dưới dạng chuỗi. Nếu chuyển toàn bộ dữ liệu thành số nguyên trước khi xử lý, "06" biến thành 6 và thay đổi bài toán. Cặp 06 cũng không phải một cách viết hợp lệ của mã 6, vì mã một chữ số không có số 0 đứng trước.

Với 2101, sau hai chữ số có hai cách: 2|1 và 21. Khi thêm 0, chỉ nhánh ghép 10 hợp lệ; nhánh này xuất phát từ tiền tố 2. Chữ số cuối 1 nối vào cách đó, còn cặp 01 bị loại. Vì vậy số cách có thể giảm khi gặp chữ số 0: từ hai cách của tiền tố 21, chỉ còn một cách cho tiền tố 210.

def decode(s):
    dp = [0] * (len(s) + 1)
    dp[0] = 1
    for i in range(1, len(s) + 1):
        if s[i - 1] != "0":
            dp[i] += dp[i - 1]
        if i >= 2 and 10 <= int(s[i - 2:i]) <= 26:
            dp[i] += dp[i - 2]
    return dp[-1]

for s in ["226", "10", "06", "2101"]:
    print(s, decode(s))

226 3
10 1
06 0
2101 1

Với chuỗi 5000 chữ số, có tối đa hai nhánh mỗi vị trí. Số phép cộng là O(n) và bảng có O(n) số. Nếu đề yêu cầu phần dư theo một mô-đun cố định, lấy dư sau mỗi phép cộng để giữ số nhỏ. Nếu yêu cầu số chính xác, số chữ số của kết quả cũng ảnh hưởng chi phí.

Lát bảng bằng cách xét phần ngoài cùng bên phải

Xét bảng cao 2 ô, rộng n cột, lát kín bằng quân domino kích thước 2 × 1. Quân có thể đặt dọc hoặc ngang. Đặt dp[i] là số cách lát bảng rộng i.

Nếu cột cuối có quân dọc, phần còn lại là bảng rộng i-1. Nếu không, hai ô cột cuối phải được phủ bằng hai quân ngang kéo sang cột trước. Khi đó phần còn lại rộng i-2. Hai cách phân loại không giao nhau và phủ mọi cách lát.

def tilings(n):
    dp = [0] * (n + 1)
    dp[0] = 1
    if n >= 1:
        dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

for width in range(6):
    print(width, tilings(width))

0 1
1 1
2 2
3 3
4 5
5 8

Bảng rộng 0 có một cách lát rỗng. Giá trị này giúp trường hợp hai cột có đủ hai lựa chọn. Với n = 1000, cần 999 phép cộng sau khi khởi tạo. Cần chú ý kích thước số nguyên như trong bài giải mã; nếu chỉ cần kết quả modulo, mỗi số được chặn bởi mô-đun.

Lỗi thường gặp

Tóm tắt

Một trạng thái tốt trả lời một câu hỏi rõ ràng. Liệt kê các cách cuối cùng để tạo trạng thái, chọn giá trị hoặc cộng số cách theo yêu cầu. Tính theo thứ tự sao cho các trạng thái cần dùng đã có. Đếm số trạng thái nhân số lựa chọn cho mỗi trạng thái để ước lượng thời gian.

Kiểm tra nhanh

Đọc thêm

• Tài liệu Python về danh sách.
• Giới thiệu quy hoạch động.