Quy hoạch động là gì? Nguyên lý hoạt động của Dynamic Programming

Trong bài viết này, Topdev sẽ giới thiệu với các bạn một thuật toán thần thánh: thuật toán quy hoạch động. Nếu bạn tham gia các cuộc thi code, bạn nhất định phải biết thuật toán này.

Gần một nửa các bài thi trong các cuộc thi code cần đến quy hoạch động. Tất nhiên, có những cách khác để giải bài toán đó. Nhưng vì các cuộc thi code đều có giới hạn về thời gian, cũng như bộ nhớ của chương trình, nên một thuật toán hiệu quả là cực kỳ cần thiết. Và trong những trường hợp như vậy, quy hoạch động là một trong những thuật toán xuất hiện nhiều nhất.

Quy hoạch động là gì?

Quy hoạch động (dynamic programming) là một phương pháp được sử dụng trong toán học và khoa học máy tính để giải quyết các vấn đề phức tạp bằng cách chia chúng thành các bài toán con đơn giản hơn. Bằng cách giải mỗi bài toán con chỉ một lần và lưu trữ kết quả, nó tránh được các phép tính dư thừa, dẫn đến giải pháp hiệu quả hơn cho nhiều bài toán.

Quy hoạch động (DP) hoạt động như thế nào?

Nguyên lý hoạt động của Dynamic Programming

1. Chia bài toán thành các bài toán con nhỏ hơn: Bài toán ban đầu được chia thành các bài toán con mà mỗi bài toán con là một phần của bài toán lớn hơn. Các bài toán con này thường có tính chất lặp lại.
2. Lưu trữ kết quả của các bài toán con: Để tránh việc tính toán lặp lại các bài toán con nhiều lần, kết quả của chúng được lưu trữ trong một bảng (thường là mảng hoặc ma trận).
3. Sử dụng lại kết quả đã lưu: Khi cần kết quả của một bài toán con nào đó, chương trình sẽ kiểm tra bảng lưu trữ để xem kết quả đã được tính toán trước đó chưa. Nếu đã có, nó sẽ sử dụng lại kết quả đó thay vì tính toán lại từ đầu.

Các bước thực hiện

1. Xác định cấu trúc của bài toán con tối ưu: Hiểu rõ cách mà bài toán lớn được chia thành các bài toán con và cách mà kết quả của các bài toán con này kết hợp lại để giải quyết bài toán lớn.
2. Định nghĩa hàm hồi quy: Xác định công thức hoặc hàm hồi quy để giải quyết bài toán dựa trên các bài toán con. Đây là bước quan trọng để hiểu cách các bài toán con liên kết với nhau.
3. Tính giá trị của bài toán con theo thứ tự từ nhỏ đến lớn: Bắt đầu từ những bài toán con nhỏ nhất và sử dụng công thức hồi quy để tính giá trị của các bài toán con lớn hơn dựa trên các bài toán con nhỏ hơn đã được tính toán trước đó.
4. Lưu trữ kết quả của các bài toán con: Kết quả của mỗi bài toán con được lưu trữ trong bảng để sử dụng lại sau này.
5. Giải quyết bài toán lớn nhất: Sau khi đã tính toán và lưu trữ kết quả của tất cả các bài toán con, sử dụng chúng để giải quyết bài toán ban đầu.

Khi nào thì dùng thuật toán quy hoạch động

Khi nào thì chúng ta cần đến quy hoạch động? Đó là một câu hỏi rất khó trả lời. Không có một công thức nào cho các bài toán như vậy.

Tuy nhiên, có một số tính chất của bài toán mà bạn có thể nghĩ đến quy hoạch động. Dưới đây là hai tính chất nổi bật nhất trong số chúng:

• Bài toán có các bài toán con gối nhau.
• Bài toán có cấu trúc con tối ưu.

Thường thì một bài toán có đủ cả hai tính chất này, chúng ta có thể dùng quy hoạch động được. Một câu hỏi rất thú vị là không dùng quy hoạch động có được không? Câu trả lời là có, nhưng nếu bạn đi thi code, bạn trượt là cái chắc. Để hiểu rõ hơn, chúng ta sẽ tìm hiểu từng tính chất một trong những phần dưới đây

Bài toán con gối nhau

Tương tự như thuật toán chia để trị, quy hoạch động cũng chia bài toán lớn thành các bài toán con nhỏ hơn. Quy hoạch động được sử dụng khi các bài toán con này được gọi đi gọi lại. Phương pháp quy hoạch động sẽ lưu kết quả của bài toán con này, và khi được gọi, nó sẽ không cần phải tính lại, do đó làm giảm thời gian tính toán.

Quy hoạch động sẽ không thể áp dụng được (hoặc nói đúng hơn là áp dụng cũng không có tác dụng gì) khi các bài toán con không gối nhau. Ví dụ với thuật toán tìm kiếm nhị phân, quy hoạch động cũng không thể tối ưu được gì cả, bởi vì mỗi khi chia nhỏ bài toán lớn thành các bài toán con, mỗi bài toán cũng chỉ cần giải một lần mà không bao giờ được gọi lại.

Một ví dụ rất điển hình của bài toán con gối nhau là bài toán tính số Fibonacci. Bài toán quá nổi tiếng rồi, chúng ta có thể tính toán số Fibonacci theo đúng công thức như sau:

def fib(n):
    if n <= 1:
        return n
    return fib(n -1) + fib(n - 2)

Nếu tính toán như trên, chúng ta rất nhiều bài toán con sẽ được tính đi tính lại, điển hình là các số fib(0) và fib(1).

Và quy hoạch động chính là một trong số những phương pháp có thể giúp chúng ta tối ưu hóa quá trình tính toán này. Mỗi bài toán con (số fib) sẽ được lưu lại trước khi tính những bài toán con lớn hơn. Nhờ đó, mà việc tính toán giảm đi đáng kể, mỗi bài toán con chỉ cần tính đúng một lần.

Một ví dụ quy hoạch động với bài toán này như sau:

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

Qua ví dụ trên, bạn đã thấy được sức mạnh vượt trội của quy hoạch động chưa? Đó cũng chính là lý do mà nó rất được ưa chuộng trong các cuộc thi lập trình, khi mà thời gian và bộ nhớ đều là hữu hạn (và thường khá nhỏ).

TÌM VIỆC LÀM NGÀNH LẬP TRÌNH

Cấu trúc con tối ưu

Cấu trúc con tối ưu là một tính chất là lời giải của bài toán lớn sẽ là tập hợp lời giải từ các bài toán nhỏ hơn.

Mình lấy một ví dụ cho dễ hiểu:

Trong bài toán tìm đường đi ngắn nhất trong đồ thị, nếu một node x nằm trên đường đi ngắn nhất giữa hai node u, v thì đường đi ngắn nhất từ u đến v sẽ là tổng hợp của đường đi ngắn nhất từ u đến x và đường đi ngắn nhất từ x đến v. Môt số thuật toán tìm đường trên đồ thị (nổi tiếng nhất có lẽ là Dijkstra) đều dựa trên tính chất này, và nó cũng áp dụng quy hoạch động.

Tính chất cấu trúc con tối ưu rất quan trọng. Nó cho phép chúng ta giải bài toán lớn dựa vào các bài toán con đã giải được. Nếu không có tính chất này, chúng ta không thể áp dụng quy hoạch động được.

Không phải bài toán nào cũng có tính chất cấu trúc con tối ưu này. Ví dụ với đồ thị sau:

Đường đi dài nhất từ q -> t sẽ là q -> r -> t hoặc q -> s -> t. Nhưng không giống như bài toán tìm đường đi ngắn nhất, đường đi dài nhất không phải là tổ hợp của những đường đi thành phần, do đó, bài toán này không có cấu trúc con tối ưu.

Ví dụ, đường q -> r -> t không phải là tổ hợp của đường đi dài nhất từ q -> r và đường đi dài nhất từ r -> t. Bởi vì, đường đi dài nhất q -> rphải là q -> s -> t -> r và đường đi dài nhất từ r -> t phải là r -> q -> s -> t.

Ưu và nhược điểm của Quy hoạch động

Ưu điểm của Dynamic Programming (DP)

Dynamic Programming có nhiều ưu điểm, bao gồm:

• Giảm thời gian tính toán: Quy hoạch động lưu trữ kết quả của các bài toán con đã được tính toán trước đó, giúp giảm thiểu đáng kể số lượng phép tính cần thực hiện. Điều này đặc biệt hiệu quả trong các bài toán có tính chất lặp lại, như dãy Fibonacci hoặc bài toán tối ưu hóa.
• Giải quyết được các bài toán phức tạp: DP cho phép giải quyết nhiều bài toán tối ưu hóa và lập lịch phức tạp mà các phương pháp khác không thể làm được hiệu quả, chẳng hạn như bài toán balo, chuỗi con chung dài nhất (LCS), và nhiều bài toán đồ thị.
• Tránh được các tính toán lặp lại không cần thiết: Bằng cách lưu trữ kết quả của các bài toán con, DP tránh được việc tính toán lặp lại những phần đã giải quyết, giúp tiết kiệm tài nguyên và tăng hiệu suất.
• Độ chính xác cao: Kỹ thuật DP đảm bảo tìm ra giải pháp tối ưu cho bài toán bằng cách xây dựng các giải pháp từ các bài toán con tối ưu.

Nhược điểm của Quy hoạch động

• Tốn bộ nhớ: DP yêu cầu lưu trữ kết quả của tất cả các bài toán con, điều này có thể tốn rất nhiều bộ nhớ, đặc biệt đối với các bài toán có không gian trạng thái lớn. Điều này có thể gây ra vấn đề khi áp dụng DP cho các bài toán có quy mô lớn.
• Phức tạp trong việc triển khai: Hiểu và triển khai một giải pháp DP đòi hỏi người lập trình phải hiểu rõ cấu trúc của bài toán và cách chia nhỏ nó thành các bài toán con. Điều này có thể phức tạp và tốn nhiều thời gian để thiết kế và debug.
• Không phải lúc nào cũng khả thi: Không phải bài toán nào cũng có thể áp dụng được DP. Các bài toán cần có tính chất con tối ưu (optimal substructure) và tính chất lặp lại của bài toán con (overlapping subproblems). Nếu bài toán không có các tính chất này, DP sẽ không hiệu quả.
• Tiêu tốn thời gian cho việc lưu trữ và truy xuất: Mặc dù giảm thời gian tính toán, việc lưu trữ và truy xuất kết quả từ bộ nhớ cũng tiêu tốn thời gian, đặc biệt khi kích thước của bảng lưu trữ lớn.

Một số bài toán quy hoạch động

Trong phần này, chúng ta sẽ làm quen với quy hoạch động thông qua một số ví dụ cụ thể. Chúng ta sẽ xem xét cách quy hoạch động được áp dụng vào các bài toán cụ thể như thế nào, đồng thời qua đó, chúng ta sẽ hiểu hơn về các tính chất ở phần trước.

Ví dụ 1: Bài toán kinh điển với đồng xu

Đây là một ví dụ rất kinh điển khi học về quy hoạch động. Có thể có nhiều cách phát biểu khác nhau nhưng về cơ bản, nội dung của nó sẽ tương tự như sau.

Giả sử chúng ta có n đồng xu nặng lần lượt là W1, W2, ..., Wn, và bài toán đặt ra là tìm số lượng đồng xu nhỏ nhất để tổng khối lượng của chúng là một giá trị S. Tất nhiên, số lượng đồng xu là không giới hạn.

Giả sử chúng ta có n đồng xu nặng lần lượt là W1, W2, ..., Wn, và bài toán đặt ra là tìm số lượng đồng xu nhỏ nhất để tổng khối lượng của chúng là một giá trị S. Tất nhiên, số lượng đồng xu là không giới hạn.

Với bài toán này, chúng ta cần xây dựng và giải các bài toán con gối nhau. Với ví dụ của chúng ta, mỗi bài toán con dp(P) với P <= S là bài toán tìm số đồng xu nhỏ nhất để khối lượng của chúng là P. và dp(P) = k chính là số lượng đồng xu nhỏ nhất đó.

Chúng ta sẽ áp dụng phương pháp quy hoạch động bằng cách bắt đầu từ bài toán con dp(0) sau đó tiếp tục với các bài toán con lớn hơn. Lời giải của các bài toán con sẽ được xây dựng lần lượt cho đến chúng ta xây dựng đến bài toán dp(S) và đó chính là kết quả của bài toán lớn. Một điều cần lưu ý với kỹ thuật này là bài toán con tiếp theo sẽ không thể giải được nếu chúng ta chưa giải bài toán con trước đó.

Cuối cùng là phần khó nhất của mọi bài toán quy hoạch động, đó là trả lời câu hỏi: cấu trúc con tối ưu của bài toán này ở đâu. Hay nói một cách khác, làm thế nào để từ những bài toán nhỏ hơn có thể tổ hợp ra lời giải cho bài toán lớn. Với vị dụ kinh điển này, mọi thứ sẽ tương đối đơn giản, nhưng với những bài toán phức tạp hơn, chúng ta cần suy nghĩ và tính toán nhiều hơn.

Quay trở lại với bài toán của chúng ta. Giả sử P là tổng khối lượng của các đồng xu nặng lần lượt là V1, V2, ..., Vj. Để có được khối lượng P, chúng ta cần thêm vài đúng 1 đồng xu nặng U vào khối lượng Q sao cho Q + U = P. Tất nhiên, bài toán con dp(Q) chúng ta đã có lời giải nên chúng ta sẽ biết được cần bao nhiêu đồng xu cho dp(P). Và vì có nhiều đồng xu U(nhiều nhưng hữu hạn) nên chúng ta có thể cần đến nhiều bài toán con trước đó, và dp(p) là giá trị nhỏ nhất sau khi tổng hợp những bài toán con đó.

Ví dụ với n = 3, S = 11, W = [1, 3, 5].

• Bắt đầu với bài toán con 0 ta có dp(0) = 0
• Với bài toán con 1, có 1 đồng xu (nặng 1) có thể thêm vào từ 0 đồng xu nào cả. Vậy dp(1) = dp(0) + 1 = 1.
• Với bài toán con 2, cũng chỉ có 1 đồng xu (nặng 1) có thể thêm vào từ 1 đồng xu. Vậy dp(2) = dp(1) + 1 = 2.
• Với bài toán con 3, chúng ta có thể thêm 1 đồng xu 3 vào 0 đồng xu hoặc thêm 1 đồng xu 1 vào 2 đồng xu. Rõ ràng là cách đầu tiên cho kết quả nhỏ hơn. Vậy dp(3) = min(dp(2) + 1, dp(0) + 1) = min(3, 1) = 1
• …
• Cứ tiếp tục như vậy cho đến bài toán S chính là đáp án chúng ta cần tìm.

Về mặt cài đặt, quy hoạch động thường lưu kết quả vào một mảng. Trong ví dụ của chúng ta, mảng dp[0..S] sẽ lưu kết quả cho từng bài toán con. Nói cách khác, dp[P] = k nghĩa là cần ít nhất k đồng xu để có khối lượng là PToàn bộ mảng này sẽ được tính bằng vòng lặp. Đoạn code sau mô tả toàn bộ quá trình này.

n, S = map(int, input().split())
w = list(map(int, input().split()))
dp = [0] * (S + 1)
dp[0] = 0

for P in range(1, S + 1):
    dp[P] = min(dp[P - x] for x in w if x <= P) + 1

print(dp)
print(dp[S])

# Nếu đầu vào như sau: n = 3, S = 11, w = [1, 3, 5]
# Thì bảng lời giải cho các bài toán con sẽ lần lượt như sau:
# P = 0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11
# ------+--+--+--+--+--+--+--+--+--+--+--
# k = 0 |1 |2 |1 |2 |1 |2 |3 |2 |3 |2 |3

Ví dụ 2: Xâu con chung dài nhất (LCS)

Thêm một ví dụ nữa cho dễ, cũng là một bài toán rất nổi tiếng.

Cho hai xâu ký tự. Tìm độ dài xâu con chung nhỏ nhất giữa chúng. Ví dụ với 2 xâu “quetzalcoatl” và “tezcatlipoca” thì xâu con chung dài nhất sẽ là “ezaloa” với độ dài 6.

Với bài toán này, chúng ta sẽ lần lượt giải các bài toán con như sau:

Lấy i ký tự đầu tiên từ xâu thứ nhất và j ký tự đầu tiên từ xâu thứ hai và tìm độ dài xâu chung dài nhất giữa 2 xâu con được lấy ra đó. Dễ dàng thấy được rằng, lời giải của mỗi bài toán con sẽ phụ thuộc vào i và j, dp(i, j). Và bài toán lớn sẽ được giải bằng cách lần lượt giải các bài toán con lần lượt từ dp(0, 0) và tăng dần độ dài xâu được lấy ra cho đến khi chúng ta lấy ra toàn bộ xâu của đề bài.

Chúng ta hãy bắt đầu lần lượt các bài toán con. Đương nhiên, nếu một trong hai xâu là rỗng thì xâu con chung của chúng cũng rỗng. Vậy dp(0, j) = dp(i, 0) = 0. Nếu cả i và j đều dương, chúng ta cần suy xét một vài trường hợp.

1. Nếu ký tự cuối cùng của xâu thứ nhất không có mặt trong xâu con chung dài nhất, nó có thể bị bỏ qua mà không ảnh hưởng gì đến kết quả. Công thức ở đây sẽ là dp(i, j) = dp(i - 1, j).
2. Tương tự như trường hợp trên, ký tự cuối cùng của xâu thứ hai không ảnh hưởng đến kết quả thì dp(i, j) = dp(i, j - 1).
3. Trường hợp cuối cùng, nếu hai ký tự cuối cùng của hai xâu x1, x2 đều có mặt trong xâu con chung dài nhất. Dĩ nhiên là hai ký tự này phải là một thì điều này mới xảy ra, tức là x1 == x2. Trong trường hợp này, khi xoá đi bất cứ một ký tự nào trong hai ký tự đó đều khiến xâu con chung dài nhất ngắn đi 1 ký tự. Vậy rõ ràng là dp(i, j) = dp(i - 1, j - 1) + 1.

Trong cả ba trường hợp trên, chúng ta phải chọn ra trường hợp nào cho kết quả là xâu con chung dài nhất (với bài toán này thì chỉ cần đưa ra độ dài đó là đủ).

Về mặt cài đặt, dp sẽ được lưu trong mảng hai chiều. Kết quả của mảng này sẽ được tính toán thông qua vòng lặp hai lớp. Lưu ý rằng, chúng ta cần thực hiện vòng lặp sao cho chúng ta sẽ giải lần lượt từng bài toán con một, theo thứ tự từ nhỏ đến lớn. Bởi vì mỗi bài toán con dp(i, j) đều phụ thuộc vào các bài toán con trước đó dp(i - 1, j), dp(i, j - 1), dp(i - 1, j - 1).

n1, n2 = map(int, input().split())
s1, s2 = input().split()
t = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
for i, x1 in enumerate(s1, 1):
    for j, x2 in enumerate(s2, 1):
        if x1 == x2:
            t[i][j] = t[i - 1][j - 1] + 1
        else:
            t[i][j] = max(t[i][j - 1], t[i - 1][j])

print(t[-1][-1])

# Kết quả khi giải các bài toán con như bảng sau:
#
#    S|    t  e  z  c  a  t  l  i  p  o  c  a
# T ji| 0  1  2  3  4  5  6  7  8  9 10 11 12
# ----+--------------------------------------
#  0 | 0  0  0  0  0  0  0  0  0  0  0  0  0
# q 1 | 0  0  0  0  0  0  0  0  0  0  0  0  0
# u 2 | 0  0  0  0  0  0  0  0  0  0  0  0  0
# e 3 | 0  0  1  1  1  1  1  1  1  1  1  1  1
# t 4 | 0  1  1  1  1  1  2  2  2  2  2  2  2
# z 5 | 0  1  1  2  2  2  2  2  2  2  2  2  2
# a 6 | 0  1  1  2  2  3  3  3  3  3  3  3  3
# l 7 | 0  1  1  2  2  3  3  4  4  4  4  4  4
# c 8 | 0  1  1  2  3  3  3  4  4  4  4  5  5
# o 9 | 0  1  1  2  3  3  3  4  4  4  5  5  5
# a 10| 0  1  1  2  3  4  4  4  4  4  5  5  6
# t 11| 0  1  1  2  3  4  5  5  5  5  5  5  6
# l 12| 0  1  1  2  3  4  5  6  6  6  6  6  6

look_up = {0: 1, 1: 1}
def fib(n):
    if look_up.get(n) is None:
        look_up[n] = fib(n - 1) + fib(n - 2)
    return look_up[n]

# Công thức đệ quy cho bài toán quy hoạch động
#   {dp[0] = 1;
#   {dp[P] = sum(dp[P-Wi]);   (for Wi <= P)
#
# Với đầu vào như sau: n = 3, S = 11, W = [1, 3, 5]
# Mảng kết quả quy hoạch động sẽ là
#  P = 0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11
#  ------+--+--+--+--+--+--+--+--+--+--+--
#  k = 1 |1 |1 |2 |3 |5 |8 |12|19|30|47|74

n, S = map(int, input().split())
w = list(map(int, input().split()))


def count(arr, x):
    # Có 1 cách (lấy ra 0 đồng xu) cho tổng khối lượng bằng 0
    if x == 0:
        return 1
    # Không thể lấy được các đồng xu cho khối lượng âm
    if x < 0:
        return 0
    # Không thể lấy nếu không có đồng xu nào
    if not arr and x >= 1:
        return 0
    # Kết quả là tổ hợp các bài toán con
    return count(arr[:-1], x) + count(arr, x - arr[-1])


print(count(w, S))

n, S = map(int, input().split())
w = list(map(int, input().split()))

dp = [[0 for _ in range(n)] for _ in range(S + 1)]
for i in range(n):
    dp[0][i] = 1

for i in range(1, S + 1):
    for j in range(n):
        x = dp[i - w[j]][j] if i - w[j] >= 0 else 0
        y = dp[i][j - 1] if j >= 1 else 0
        dp[i][j] = x + y


print(dp[-][n - 1])
# Kết quả tính toán với n = 3, w = [1, 3, 5] như sau:
#  S = 0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11
#  ------+--+--+--+--+--+--+--+--+--+--+--
#  k = 1 |1 |1 |2 |2 |3 |4 |4 |5 |6 |7 |8

n1, n2 = map(int, input().split())
s1, s2 = input().split()
s1 += 'x00'
s2 += 'x00'

# Điền sẵn giá trị trung tính
dp = [[-1] * (n1 + 2) for _ in range(n2 + 2)]
dp[0][0] = 0

for i in range(n1 + 1):
    for j in range(n2 + 1):
        tres = dp[i][j]
        # Phát triển theo hướng thứ nhất
        if dp[i + 1][j] < tres:
            dp[i + 1][j] = tres
        # Phát triển theo hướng thứ hai
        if dp[i][j + 1] < tres:
            dp[i][j + 1] = tres
        # Phát triển theo hướng thứ ba
        if s1[i] == s2[j] and dp[i + 1][j + 1] < tres + 1:
            dp[i + 1][j + 1] = tres + 1

print(dp[n1][n2])