Giới thiệu về Dynamic Programming (DP)

Trong hành trình giải các bài toán trên LeetCode, Dynamic Programming (DP) hay còn gọi là Quy hoạch động trong tiếng Việt, là một trong những dạng bài phổ biến nhất nhưng cũng khó khăn nhất. Khi bạn nhận diện được một bài toán có thể giải quyết bằng DP, bạn đã hoàn thành 80% công việc. Trong bài viết này, chúng ta sẽ khám phá 5 dạng bài DP phổ biến trên LeetCode, giúp bạn dễ dàng nhận diện và giải quyết chúng.

1. Tìm giá trị nhỏ nhất / lớn nhất

Đề bài

Cho một mục tiêu, tìm giá trị nhỏ nhất / lớn nhất để đạt được mục tiêu đó.

Hướng giải

Tính giá trị nhỏ nhất/lớn nhất trong tổng số các phương án có thể, sau đó cộng với giá trị của trạng thái hiện tại.

routes[i] = min(routes[i-1], ... , routes[i-k]) + cost[i]

Khi giải một bài toán DP, chúng ta có 2 hướng tiếp cận: Top-Down và Bottom-Up.

• Top-Down: Bắt đầu từ bài toán lớn nhất và sử dụng đệ quy để giải quyết các bài toán nhỏ hơn, kết quả được lưu trữ trong mảng memo để tránh tính toán thừa.
• Bottom-Up: Giải quyết các bài toán nhỏ trước và sử dụng các kết quả này để tính toán bài toán lớn hơn.

Áp dụng vào bài Min Cost Climbing Stairs

Đề bài yêu cầu xác định chi phí nhỏ nhất để leo hết cầu thang với chi phí tương ứng ở mỗi bước.

Chúng ta có thể xác định chi phí nhỏ nhất để đến bước i như sau:

if (ways[j] <= i) {
    dp[i] = min(dp[i], dp[i - ways[j]] + cost[i]);
}

Cách giải Top-Down và Bottom-Up cũng được áp dụng tương tự như trước.

2. Tìm số cách khác nhau

Đề bài

Cho một mục tiêu, tìm số cách khác nhau để đạt được mục tiêu.

Hướng giải

Tính tổng tất cả các cách có thể để đạt được mục tiêu này.

routes[i] = routes[i-1] + routes[i-2] + ... + routes[i-k]

Áp dụng vào bài Climbing Stairs

Cho cầu thang cần n bước, tìm số cách khác nhau để leo lên đến đỉnh.

Giải pháp tương tự như trên bằng Top-Down và Bottom-Up.

3. Hợp nhất các khoảng giá trị

Đề bài

Tìm giải pháp tối ưu cho một bộ số, xét số hiện tại cùng với kết quả tốt nhất từ bên trái và bên phải.

Hướng giải

Tìm tất cả giải pháp tối ưu cho mỗi khoảng và trả về kết quả tốt nhất.

Áp dụng vào bài Minimum Cost Tree From Leaf Values

Tìm cây nhị phân có tổng node không phải lá nhỏ nhất.

4. Xử lý chuỗi

Các bài toán liên quan đến chuỗi thường có 1 hoặc 2 chuỗi với độ dài không quá lớn.

Hầu hết đều có thể giải được với độ phức tạp thời gian là O(n).

Ví dụ: Longest Common Subsequence

Tìm chiều dài lớn nhất của subsequence chung giữa 2 chuỗi.

Áp dụng vào bài Palindromic Substrings

Tính số lượng palindromic substring của một string.

5. Ra quyết định

Đề bài

Cho một tập giá trị, tìm đáp án chọn hoặc bỏ qua giá trị hiện tại.

Hướng giải

Xác định kết quả dựa trên quyết định chọn hoặc không chọn giá trị hiện tại.

Áp dụng vào bài House Robber

Tính số tiền tối đa có thể trộm mà không bị báo cảnh sát.

Kết luận

Thông qua bài viết này, hy vọng bạn sẽ dễ dàng nhận diện và giải quyết các dạng bài Dynamic Programming trên LeetCode. Việc nắm vững các phương pháp này sẽ giúp bạn tự tin hơn trong các bài kiểm tra và phỏng vấn.

Tham khảo

• LeetCode Discuss - Dynamic Programming Patterns

🔔 Blog: henrytechie.com
☕️ Facebook: Henry Techie
☁️ TikTok: @henrytechie
source: viblo