Bài đăng gốc: https://manhhomienbienthuy.github.io/2017/08/24/algorithm-quy-hoach-dong.html (Yêu cầu có sự cho phép)
Trong bài viết này, tôi sẽ giới thiệu với các bạn một thuật toán siêu đẳng: lập trình động. Nếu bạn tham gia các cuộc thi mã hóa, bạn phải biết thuật toán này.
Gần một nửa số bài kiểm tra trong các cuộc thi lập trình yêu cầu lập trình động. Tất nhiên, có nhiều cách khác để giải quyết vấn đề này. Nhưng vì các cuộc thi mã hóa bị hạn chế về thời gian và bộ nhớ của chương trình, nên các thuật toán hiệu quả là rất cần thiết. Trong bối cảnh này, lập trình động là một trong những thuật toán phổ biến nhất.
Thuật toán quy hoạch động được ưa chuộng hơn vì ban đầu bài toán có nhiều dạng và phải suy nghĩ nhiều mới tìm ra lời giải. Không có một công thức chuẩn duy nhất nào phù hợp với mọi vấn đề. Do tính phổ biến của nó, bạn phải rất thành thạo thuật toán này nếu muốn thi đấu tốt.
Cách hiệu quả nhất để học một thuật toán là xem xét các ví dụ cụ thể. Trong bài viết này, tôi sẽ giới thiệu một số ví dụ trong các phần sau. Nó có thể không đầy đủ, bạn có thể đọc các bài viết khác. Mình giới thiệu với các bạn một tài liệu rất hay: Dynamic Programming: From Novice to Advanced
Khi nào chúng ta cần lập trình động? Đây là một câu hỏi khó trả lời. Không có công thức cho những câu hỏi như vậy.
Tuy nhiên, bạn có thể nghĩ đến một số tính chất của bài toán trong quy hoạch động. Đây là hai trong số những điều nổi bật nhất:
- Một câu hỏi có các câu hỏi con chồng lên nhau
- Bài toán cấu trúc con tối ưu
- Bắt đầu từ bài toán con 0, ta có dp(0) = 0
- Đối với bài toán con 1, có 1 đồng xu (trọng lượng 1) có thể được thêm vào từ 0 đồng xu. Vậy dp(1) = dp(0) + 1 = 1.
- Đối với bài toán con 2, 1 đồng xu chỉ có thể thêm 1 đồng xu (trọng số 1). Vậy dp(2) = dp(1) + 1 = 2.
- Đối với bài toán con 3, chúng ta có thể cộng 1 đồng 3 với 0 đồng hoặc 1 đồng 1 với 2 đồng. Rõ ràng, phương pháp đầ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
- …
- Và cứ như vậy cho đến khi câu hỏi s là câu trả lời mà chúng ta cần.
- Nếu ký tự cuối cùng của chuỗi đầu tiên không nằm trong chuỗi con chung dài nhất, nó có thể được bỏ qua mà không ảnh hưởng đến kết quả. Công thức ở đây là dp(i, j) = dp(i – 1, j).
- Tương tự như trên, nếu ký tự cuối cùng của chuỗi thứ hai không ảnh hưởng đến kết quả thì dp(i, j) = dp(i, j – 1).
- Trường hợp cuối cùng, nếu 2 ký tự cuối của 2 xâu x1, x2 xuất hiện trong xâu con chung dài nhất. Tất nhiên, hai ký tự phải là một để điều này xảy ra, tức là x1 == x2. Trong trường hợp này, việc loại bỏ một trong hai ký tự sẽ rút ngắn chuỗi con chung dài nhất xuống 1 ký tự. Rõ ràng dp(i, j) = dp(i – 1, j – 1) + 1.
- Dễ viết mã hơn
- Không cần thứ tự tính toán
- Chỉ tính những gì cần thiết
- Chỉ có một cách duy nhất để duyệt
- Thường chậm hơn lập trình động.
- Số cách lấy đồng xu từ đồng xu thứ n, nghĩa là chúng ta giả sử không có đồng xu nào nặng nhất
- Số cách lấy đồng xu chứa đồng xu nặng nhất.
- dp(0,0) = 0 là vấn đề của hai chuỗi rỗng
- Với mỗi bài toán dp(i, j), chúng ta sẽ tìm cách tính kết quả của bài toán lớn hơn. Đến đây, có 3 bước phát triển tiếp theo:
- Lấy thêm một ký tự từ chuỗi đầu tiên =>; kết quả không thay đổi.
- Lấy thêm một ký tự từ chuỗi thứ hai => kết quả không thay đổi.
- Nếu ký tự tiếp theo của hai chuỗi giống nhau => lấy từ này và thêm 1 vào độ dài của chuỗi con chung.
Đây là mã cho câu hỏi này:
Hy vọng qua bài viết này mình đã giới thiệu một số phương pháp lập trình động. Về cơ bản, đối với bất kỳ bài toán quy hoạch động nào, chúng ta có thể xây dựng các bài toán con chồng chéo với cấu trúc con tối ưu cho 90% công việc được thực hiện.
Tuy nhiên, cũng cần hiểu rằng lập trình động, tuy là thuật toán thần thánh có thể giải được nhiều bài toán, nhưng không phải là thuốc chữa bách bệnh. Có một điều rõ ràng rằng cách tốt nhất để giải bất kỳ bài toán nào trong tin học là biết sử dụng và kết hợp linh hoạt nhiều thuật toán, chúng ta không nên cuồng một thuật toán, cũng không nên coi thường bất kỳ một thuật toán nào.
Nói chung, đối với các bài toán thuộc cả hai bản chất, chúng ta có thể sử dụng quy hoạch động. Một câu hỏi rất thú vị là có thể thực hiện được mà không cần sử dụng quy hoạch động hay không? Câu trả lời là có, nhưng nếu bạn tham gia kỳ thi mã hóa, bạn chắc chắn sẽ trượt. Để hiểu rõ hơn, chúng ta sẽ xem xét từng thuộc tính này trong các phần sau
Vấn đề chồng chéo
Tương tự như thuật toán chia để trị, quy hoạch động cũng chia một 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 gọi đi gọi lại các bài toán con này. Phương pháp quy hoạch động sẽ lưu kết quả của bài toán con và không cần tính toán lại khi gọi, giúp giảm thời gian tính toán.
Lập trình động sẽ không hoạt động (hay nói đúng hơn là không hoạt động) khi các bài toán con không trùng nhau. Chẳng hạn với thuật toán tìm kiếm nhị phân, lập trình động hoàn toàn không thể tối ưu được, vì mỗi lần chia nhỏ bài toán lớn thành các bài toán con, mỗi bài toán chỉ cần giải một lần và không bao giờ gọi lại.
Một ví dụ điển hình của các bài toán chồng chéo là bài toán tính các số Fibonacci. Bài toán này quá nổi tiếng, chúng ta có thể tính số Fibonacci theo công thức sau:
Nếu tính như trên, chúng ta sẽ có nhiều bài toán con cần tính lại, thường là các số fib(0) và fib(1).
Lập trình động là một trong những phương pháp có thể giúp chúng ta tối ưu hóa việc tính toán này. Mỗi bài toán con (số sợi) sẽ được lưu trước khi tính toán bài toán con lớn hơn. Kết quả là khối lượng tính toán giảm đi rất nhiều và mỗi bài toán con chỉ cần được tính toán chính xác một lần.
Một ví dụ lập trình động cho vấn đề này như sau:
Qua những ví dụ trên bạn đã thấy sức mạnh phi thường của quy hoạch động chưa? Đây là lý do tại sao nó rất phổ biến trong các cuộc thi lập trình khi thời gian và bộ nhớ bị hạn chế (và thường là nhỏ).
Cấu trúc con tối ưu
Cấu trúc con tối ưu là thuộc tính mà giải pháp cho một vấn đề lớn là tập hợp các giải pháp cho một vấn đề nhỏ.
Để dễ hiểu, tôi xin đưa ra một ví dụ:
Trong bài toán tìm đường đi ngắn nhất trong đồ thị, nếu một nút x nằm trên đường đi ngắn nhất giữa hai nút u, v thì đường đi ngắn nhất từ u đến v bằng tổng các đường đi ngắn nhất từ u đến v x và Đường đi ngắn nhất từ x đến v. Một số thuật toán tìm đường đồ thị (nổi tiếng nhất có lẽ là Dijkstra) dựa trên thuộc tính này, cũng áp dụng lập trình động.
Tính chất cấu trúc con tối ưu là rất quan trọng. Nó cho phép chúng ta giải các bài toán lớn dựa trên các bài toán con đã giải. Không có tính chất này, chúng ta không thể áp dụng quy hoạch động.
Không phải bài toán nào cũng có thuộc tính cấu trúc con tối ưu này. Ví dụ trong hình bên dưới:
Đường dẫn 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 đường đi ngắn nhất, đường đi dài nhất không phải là một tập hợp của các đường thành phần, vì vậy bài toán không có cấu trúc con tối ưu.
Ví dụ: đường q -> r -> t không phải là sự kế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 -> r phải là q -> s -> t -> r và đường đi dài nhất từ r -> t phải là r -> q -> s ->
Trong phần này, chúng ta sẽ làm quen với lập trình động thông qua một số ví dụ cụ thể. Chúng ta sẽ thấy cách lập trình động được áp dụng cho một bài toán cụ thể, và qua đó, chúng ta sẽ hiểu rõ hơn các tính chất từ phần trước.
Ví dụ 1: Bài toán cổ điển về đồng xu
Đây là một ví dụ rất kinh điển khi học lập trình động. Có thể nói theo nhiều cách 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 với các trọng lượng w1,w2,…,wn và bài toán đặt ra là tìm số lượng xu nhỏ nhất sao cho tổng khối lượng của chúng là giá trị s. Tất nhiên, số lượng xu là không giới hạn.
Với bài toán này ta cần xây dựng và giải bài toán chồng lớp. Ví dụ của chúng ta, mỗi bài toán con dp(p) trong đó p <= s là bài toán tìm số lượng đồng xu nhỏ nhất sao cho chúng có khối lượng p. dp(p) = k là số xu tối thiểu.
Chúng ta sẽ bắt đầu áp dụng phương pháp quy hoạch động với bài toán con dp(0) rồi chuyển sang các bài toán con lớn hơn. Lời giải cho các bài toán con sẽ được xây dựng tuần tự cho đến khi chúng ta xây dựng được dp(s) bài toán, đây là kết quả của bài toán lớn hơn. Một điều cần nhớ với kỹ thuật này là nếu chúng ta không giải bài toán con trước thì bài toán con tiếp theo sẽ không được giải.
Cuối cùng, phần khó nhất của bất kỳ bài toán lập trình động nào là trả lời câu hỏi: đâu là cấu trúc con tối ưu cho bài toán này. Hay nói cách khác là cách kết hợp các vấn đề nhỏ hơn để giải quyết các vấn đề lớn. Với ví dụ kinh điển này, mọi thứ sẽ tương đối đơn giản, nhưng khi gặp những vấn đề phức tạp hơn, chúng ta cần tư duy và tính toán nhiều hơn.
Trở lại câu hỏi của chúng ta. Giả sử p lần lượt là tổng khối lượng các đồng xu nặng v1, v2, …, vj. Để có khối lượng p, chúng ta cần cộng một số đồng xu có trọng lượng chính xác u với khối lượng q sao cho q + u = p. Tất nhiên, chúng ta đã biết bài toán con dp(q), vì vậy chúng ta biết dp(p) cần bao nhiêu xu. Và vì có nhiều xu u (nhiều nhưng hữu hạn) nên chúng ta có thể cần nhiều bài toán con trước, dp(p) là giá trị nhỏ nhất sau khi tính tổng các bài toán con này.
Ví dụ n = 3, s = 11, w = [1, 3, 5].
Khi triển khai, lập trình động thường lưu trữ kết quả trong một mảng. Trong ví dụ của chúng ta, mảng dp[0..s] sẽ lưu kết quả của từng bài toán con. Nói cách khác, dp[p] = k có nghĩa là cần có ít nhất k đồng xu để có khối lượng là p và toàn bộ mảng sẽ được tính toán thông qua vòng lặp. Đoạn mã dưới đây mô tả toàn bộ quá trình.
Ví dụ 2: Chuỗi con chung dài nhất (lcs)
Lấy thêm một ví dụ nữa cho tiện, đây cũng là một bài toán quen thuộc.
Cho hai chuỗi. Tìm độ dài của xâu con chung nhỏ nhất giữa chúng. Ví dụ: đối với 2 chuỗi “quetzalcoatl” và “tezcatlipoca”, chuỗi con chung dài nhất sẽ là “ezaloa” có độ dài 6.
Với vấn đề này, chúng ta sẽ lần lượt giải quyết các vấn đề con sau:
Trích xuất i ký tự đầu tiên từ chuỗi đầu tiên, j ký tự đầu tiên từ chuỗi thứ hai và tìm độ dài của chuỗi chung dài nhất giữa hai chuỗi con được trích xuất. Dễ thấy rằng lời giải cho mỗi bài toán con sẽ phụ thuộc vào i và j, dp(i, j). Bắt đầu từ dp(0, 0), các bài toán con được giải lần lượt và độ dài của chuỗi trích được tăng dần cho đến khi thu được toàn bộ chuỗi của bài toán, từ đó giải được bài toán lớn.
Hãy bắt đầu với từng câu hỏi phụ. Tất nhiên, nếu một trong các chuỗi trống, chuỗi con chung của chúng cũng trống. Vậy dp(0, j) = dp(i, 0) = 0. Nếu cả i và j đều dương, chúng ta cần xem xét một số trường hợp.
Trong cả 3 trường hợp trên, ta phải chọn cái nào cho ra xâu con chung dài nhất (bài toán này chỉ cần cho độ dài đó là đủ).
Khi triển khai, dp sẽ được lưu trữ trong một mảng hai chiều. Kết quả của mảng này sẽ được tính toán thông qua hai lớp vòng lặp. Lưu ý rằng chúng ta cần lặp lại để giải từng bài toán con theo thứ tự từ nhỏ nhất đến lớn nhất. Vì mỗi bài toán con dp(i, j) 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) .
Có một kỹ thuật khác gọi là “ghi nhớ” có cách tiếp cận tương tự như lập trình động. Cả lập trình động và ghi nhớ đều được sử dụng để tối ưu hóa các vòng lặp với các phép tính tương tự, trong đó kết quả của một phép tính lớn hơn cần được tính từ kết quả của một phép tính nhỏ hơn. Ghi nhớ thường được sử dụng trong tính toán đệ quy, trong đó tính toán được lặp lại nhiều lần. Nó sẽ lưu một bảng các giá trị được tính toán và mỗi khi có một phép tính cần thực hiện, trước tiên chúng ta sẽ tra cứu bảng. Nếu bảng đã có kết quả thì ta chỉ cần tìm nạp, nếu chưa có ta tính như bình thường và tiếp tục lưu vào bảng.
ghi nhớ không thực sự là một thuật toán, nó là một kỹ thuật được sử dụng trong lập trình. Để hiểu rõ hơn về kỹ thuật này, tôi xin đưa ra ngay một ví dụ về bài toán Fibonacci. Chúng ta sẽ sử dụng bộ nhớ như sau:
Sự khác biệt chính là lập trình động sẽ thực hiện các phép tính theo thứ tự được xác định trước, trong khi quá trình ghi nhớ thực hiện một quá trình truyền tải sâu. Lập trình động không bao giờ đánh giá một bài toán con hai lần, tương tự như tính toán đệ quy sử dụng bộ nhớ. Tuy nhiên, ghi nhớ không bao giờ tính toán các hoạt động dư thừa, trong khi lập trình động sẽ yêu cầu tất cả các bài toán con. Đây là một phương pháp thực sự thú vị chỉ tính toán những gì cần thiết và lưu kết quả này để sử dụng lại sau này trong các cuộc gọi mà không cần tính toán thêm.
Tính năng ghi nhớ có một số ưu điểm và nhược điểm so với lập trình động:
Lợi thế
Nhược điểm
Hầu hết các bài toán quy hoạch động có thể được chia thành hai loại: bài toán yêu cầu quy hoạch động để tối ưu hóa và bài toán tổ hợp. Trong các phần tiếp theo, chúng ta sẽ xem xét riêng từng loại vấn đề này.
Vấn đề tối ưu hóa
Các bài toán tối ưu hóa yêu cầu chúng ta tìm ra câu trả lời tốt nhất từ mục tiêu của bài toán. Cả hai ví dụ mà tôi đưa ra ở trên đều là các bài toán thuộc loại này (một bài tìm số xu tối thiểu và một bài tìm chuỗi con dài nhất). Mối quan hệ cho các bài toán con như vậy có công thức dp[s] = min(f1(dp[i], dp[j], …, dp[k]), f2(dp[u) ], dp[v ], …, dp[w]), …, fl(dp[q], dp[p], …, dp[z])), trong đó mảng dp lưu trữ kết quả của các bài toán con đó.
Mỗi vấn đề được giải quyết dựa trên các vấn đề đã được giải quyết trước đó. Đây là thuộc tính cấu trúc con tối ưu cho từng bài toán. Đối với các bài toán về đồng xu, mỗi bài toán mới được giải bằng cách thêm đúng 1 đồng xu vào kết quả của bài toán trước. Kết quả cuối cùng là kết quả tốt nhất bạn có thể nhận được bằng cách thêm các đồng xu có trọng lượng khác nhau theo một số cách.
Mảng kết quả có thể được điền với một số giá trị trung lập trước khi tính toán. Giá trị trung lập có nghĩa là nó sẽ không bao giờ là câu trả lời cho bất kỳ câu hỏi phụ nào. Ví dụ: khi chúng ta cần tìm số xu tối thiểu, chúng ta có thể điền vào mảng này số dương lớn nhất và mọi phép tính tiếp theo sẽ cho kết quả nhỏ hơn. Nếu không tìm thấy kết quả nào khác, chúng ta có thể cho rằng bài toán con không giải được.
Câu hỏi kết hợp
Các bài toán tổ hợp thường yêu cầu chúng ta tìm nhiều cách khác nhau để làm một việc nào đó. Nhiều bài kiểm tra mã hóa thường có kết quả rất lớn và chúng yêu cầu chúng tôi đưa ra câu trả lời theo modulo 10000007. Trong loại bài toán này, công thức xây dựng các bài toán con sẽ là r[s] = f1(r[ i], r[j], . . . , r[k]) + f2(r[u], r[ v ], …, r[w]) + … + fl(r[q] , r[p], … , r[z]).Sự khác nhau cơ bản giữa dạng bài toán này và bài toán tối ưu là chúng ta Yêu cầu tính tổng thay vì tìm số lớn nhất hoặc nhỏ nhất.
Trong mọi bài toán quy hoạch động, tính chất cấu trúc con tối ưu luôn là quan trọng nhất và khó đảm bảo nhất. Nếu cấu trúc con không được tối ưu, chúng ta sẽ tính toán sai và tất nhiên kết quả sẽ không chính xác.
Đối với hầu hết các bài toán quy hoạch động, việc phân chia các bài toán con trùng nhau là dễ dàng, nhưng việc đảm bảo cấu trúc con tối ưu thì khó hơn nhiều.
Tôi sẽ nêu thêm hai ví dụ tương tự để mọi người hiểu rõ hơn về sự khó khăn trong việc bảo vệ tài sản này.
Vẫn là bài toán đồng xu, hãy biến tấu một chút để được bài toán tổ hợp sau:
Tìm số cách khác nhau để chọn các đồng xu sao cho tổng khối lượng của chúng là s.
Bài toán con giống như bài trước: dp(p) = k là số cách khác nhau để chọn đồng xu có tổng khối lượng p. Công thức đệ quy trong ví dụ này thay đổi theo các câu hỏi sau:
Câu hỏi kết hợp cũng có thể có giá trị trung tính. Vì các bài toán tổ hợp thường được tính tổng nên giá trị trung tính sẽ là 0. Các bài toán tổ hợp yêu cầu tìm nhiều cách khác nhau để làm một việc gì đó, vì vậy giá trị 0 không ảnh hưởng đến câu trả lời. Điều đặc biệt quan trọng trong bài toán tổ hợp này là chúng ta chỉ tính mỗi phương một lần. Nói thì dễ, nhưng trong thực tế, chúng ta thường mắc lỗi ở chỗ cực kỳ quan trọng này.
Tiếp tục biến đổi thêm một chút nữa ta sẽ có các câu hỏi tổ hợp như sau:
Tìm số cách khác nhau để chọn các đồng xu sao cho tổng khối lượng của chúng là s. Với điều kiện là các đồng tiền thu được theo cách sao cho các hoán vị không được coi là khác nhau.
Câu hỏi này khó hơn câu hỏi trước một chút. Nếu vẫn chia các bài toán con như trước thì không thể có được cấu trúc con tối ưu. Ví dụ: xu 1, 3, 5 rồi (1, 3) và (3, 1) đều ra 4 nhưng chỉ được coi là một chiều.
Với bài toán này, chúng ta phân tích bài toán lớn thành các bài toán con theo những cách tương đối khác nhau. Ta thấy rằng kết quả (số cách chọn đồng xu) sẽ là tổng của hai kết quả:
Kết quả sẽ là tổng của hai kết quả trên. Bạn thấy đấy, với cách xây dựng bài toán con này, chúng ta xây dựng các bài toán con chồng chéo mà vẫn đảm bảo một cấu trúc con tối ưu (kết quả bằng tổng các bài toán con).
Nhân tiện, với cách chia bài toán như vậy, chúng ta có thể nhận được lời giải sau thông qua phép đệ quy đơn giản:
Tuy nhiên, như tôi đã nói trong phần trước, nếu bạn đang tham gia một cuộc thi viết mã, cách tiếp cận này sẽ không mang lại cho bạn bất kỳ hy vọng chiến thắng nào vì nó tốn rất nhiều thời gian và trí nhớ. Tuy nhiên, sau khi có được cấu trúc con tối ưu của bài toán chồng lớp, chúng ta có thể dễ dàng áp dụng quy hoạch động cho bài toán này:
Bạn thấy đấy, việc xây dựng các bài toán con chồng chéo sao cho cấu trúc con vẫn tối ưu thường không hề đơn giản chút nào. Mỗi bài toán quy hoạch động đều có các phép biến đổi khác nhau không tuân theo một khuôn mẫu nghiêm ngặt nào. Ngay cả khi bạn có thể giải quyết nhiều vấn đề lập trình động, không có gì đảm bảo rằng bạn có thể giải quyết những vấn đề khác. Đây là một trong những lý do khiến những dạng bài này luôn “hot” trong cuộc thi.
Tất cả các ví dụ tôi trình bày ở trên đều sử dụng kiểu lập trình động “nghịch đảo”. Điều ngược lại ở đây không phải là chúng ta duyệt các bài toán con từ lớn đến nhỏ. Nhưng quy trình là thế này: lặp lại tất cả các bài toán con (từ nhỏ đến lớn) và với mỗi bài toán con, chúng tôi tính toán kết quả dựa trên bài toán con trước đó. Tất nhiên, các bài toán con trước đó đã được giải theo trình duyệt, và với mỗi bài toán, chúng ta lại phải “nhìn lại” bài toán trước nên gọi là quy hoạch động “ngược”.
Phương pháp lập trình động lùi này được sử dụng rộng rãi vì nó rất phù hợp với suy nghĩ tự nhiên của chúng ta. Chúng tôi đọc vấn đề và suy nghĩ về cách giải quyết nó. Giải pháp yêu cầu giải các bài toán nhỏ hơn, như làm toán hàng ngày để chứng minh các bổ đề. Chúng ta tiếp tục suy nghĩ về các bài toán con này, rồi tổng hợp lại để tìm ra giải pháp cho bài toán lớn hơn. Quá trình này cứ lặp đi lặp lại và lập trình động “nghịch đảo” này được xây dựng theo cách này.
Ngoài ra, về mặt chương trình, kiểu lập trình động này có mối quan hệ chặt chẽ với đệ quy. Nếu một bài toán lớn được giải dựa trên các bài toán con tương tự (và giống với) của bài toán lớn, thì việc áp dụng đệ quy có thể là một cách dễ dàng để viết mã cho nó. Vì vậy, trong nhiều trường hợp, có thể coi quy hoạch động là một cách tối ưu hóa phương pháp đệ quy để giải quyết vấn đề.
Ngoài quy hoạch động lùi này, còn có quy trình động “tiến”. Mặc dù nó không phổ biến và loại lập trình động khó áp dụng hơn, nhưng lập trình động “hướng xuống” đã mang lại cho chúng ta rất nhiều tiện lợi. Kiểu chuyển tiếp này cũng yêu cầu duyệt các bài toán con từ nhỏ đến lớn, nhưng với mỗi bài toán con ta tính kết quả và từ đó tìm cách thực hiện một số tính toán để giải bài toán lớn hơn. Đó là, đối với mỗi bài toán con, chúng tôi mong đợi cách giải bài toán tiếp theo như vậy bắt đầu từ bài toán hiện tại.
Phương pháp này khó áp dụng hơn phương pháp kia và không phải vấn đề nào cũng áp dụng được. Đối với mỗi vấn đề, việc xác định bước tiếp theo là tương đối khó và thậm chí không dễ để kiểm tra tính đúng đắn của phương pháp.
Như chúng ta đã thấy trong các phần trước, nói chung, mỗi bài toán cần được giải bằng cách tổng hợp kết quả của một số bài toán con trước đó. Vì vậy, loại lập trình động chuyển tiếp này chỉ sử dụng một bài toán con để tính toán trước bài toán tiếp theo sẽ chỉ cho kết quả một phần chứ không phải kết quả cuối cùng. Do đó, để thực hiện lập trình thuận động, một mảng các giá trị trung lập cần được điền trước (sau đó chúng ta sẽ cộng kết quả mỗi khi giải một bài toán con mới).
Tôi nhận bài toán về chuỗi con chung dài nhất. Đối với vấn đề này, chúng ta có thể chọn giá trị trung tính là âm. Chúng ta sẽ tìm cách lập kế hoạch cho chuyển động tịnh tiến như vậy:
