Giả sử bạn đang thực hiện một số tính toán bằng phương pháp sử dụng một loạt nguồn vào thích hợp. Có một số tính toán được thực hiện ở mọi trường hợp để rút ra một số kết quả. Bạn không biết rằng bạn đã gặp cùng một kết quả khi chúng ta cung cấp cùng một nguồn vào. Vì vậy, nó giống như bạn đang thực hiện tính toán lại một kết quả mà trước này đã đạt được bằng nguồn vào cụ thể cho đầu ra tương ứng của nó. Nhưng vấn đề ở đây là gì? Đó là việc thời kì quý báu của bạn bị lãng phí. Bạn cũng có thể dễ dàng xử lý vấn đề ở đây bằng phương pháp lưu giữ các bản ghi khớp với những tính toán trước đó. Ví như sử dụng cấu trúc tài liệu phù hợp. Ví dụ: bạn cũng có thể lưu trữ nguồn vào dưới dạng khóa và đầu ra dưới dạng giá trị.

Bạn Đang Xem: Giới thiệu về thuật toán: Dynamic Programming

Hiện nay bằng phương pháp phân tích vấn đề, lưu trữ nguồn vào của nó nếu nó mới (hoặc không có trong cấu trúc tài liệu) với đầu ra tương ứng. Trường hợp còn sót lại kiểm tra khóa nguồn vào đó và nhận đầu ra kết quả từ giá trị của nó. Bằng phương pháp đó khi chúng ta thực hiện một số tính toán và kiểm tra xem nguồn vào đó có tồn tại trong cấu trúc tài liệu đó không, bạn cũng có thể trực tiếp nhận được kết quả. Do đó tất cả chúng ta có thể liên hệ phương pháp này với những kỹ thuật lập trình động.

Đi sâu vào lập trình động

Tóm lại, tất cả chúng ta nói theo cách khác rằng lập trình động được sử dụng chủ yếu để tối ưu hóa các vấn đề, trong đó tất cả chúng ta muốn tìm ra cách tốt nhất để làm một điều gì đó.

Phần lớn các vấn đề về lập trình động có thể được phân loại thành hai loại:

1. Các bài toán con chồng chéo
2. Cấu trúc tối ưu

Trong nội dung bài viết này, tất cả chúng ta sẽ thảo luận chi tiết cụ thể về tính chất trước hết (Các bài toán con chồng chéo) một cách chi tiết cụ thể.

Một kịch bản cụ thể như các bài toán con xẩy ra tuần tự có những bài toán con nhỏ hơn của riêng chúng. Thay vì xử lý việc tái diễn của rất nhiều bài toán con, lập trình động xử lý mỗi bài toán con nhỏ hơn một lần duy nhất. Sau đó, bạn ghi lại các kết quả trong một bảng mà từ đó có thể thu được giải pháp cho vấn đề ban sơ.

Chẳng hạn, các số Fibonacci 0, 1, 1, 2, 3, 5 ,8, 13, có một mô tả đơn giản trong đó mỗi term có liên quan đến hai term trước nó. Nếu F(n) là term thứ n của dãy thì ta có F(n) = F(n – 1) + F(n – 2). Đây được gọi là công thức đệ quy hay quan hệ tái diễn. Nó cần các term trước này đã được tính toán để tính toán một term sau.

Các bài toán con chồng chéo

Xem Thêm : Nhân sinh là gì? Nhân sinh quan là gì? Triết lý nhân sinh quan?

Lập trình động chủ yếu được sử dụng lúc các giải pháp của cùng một bài toán con được cần lặp đi tái diễn. Trong lập trình động, các giải pháp được tính toán cho những bài toán con được lưu trữ trong một bảng để việc tính toán không phải tái diễn. Vì vậy, lập trình động không hữu ích khi không có những bài toán con (chồng chéo) chung vì không có điểm lưu trữ các giải pháp nếu chúng không cấp thiết nữa.

Cách tiếp cận để xử lý: top-down vs bottom-up

Có hai cách khác nhau chính sau đây để xử lý vấn đề:

Top-down: Bạn xuất phát điểm từ trên xuống, xử lý vấn đề tuần tự. Nếu như bạn thấy rằng vấn đề đã được xử lý, thì chỉ có trả lại lời giải đáp đã lưu. Điều này được gọi là Memoization.

Bottom-up: Bạn trực tiếp mở màn giải các bài toán con nhỏ hơn để tiến lên đỉnh để tìm ra giải pháp cuối cùng cho một vấn đề lớn đó. Trong quá trình này, đảm nói rằng các bài toán con được xử lý trước lúc xử lý vấn đề. Điều này còn có thể được gọi là Tabulation

Memoization

Lý do rõ ràng cho thuật toán đệ quy bị trễ là vì nó tính toán các số Fibonacci giống nhau nhiều lần.

Tất cả chúng ta có thể tăng tốc thuật toán đệ quy đáng kể chỉ bằng phương pháp viết ra kết quả của rất nhiều cuộc gọi đệ quy. Sau đó tất cả chúng ta có thể tìm kiếm chúng một lần nữa nếu tất cả chúng ta cần chúng sau này.

Memoization đề cập đến kỹ thuật lưu trữ và sử dụng lại các kết quả được tính toán trước đó.

Xem Thêm : XRP Coin là gì? Lợi ích, ưu điểm và ứng dụng của đồng XRP hiện tại

Tất cả chúng ta khởi tạo một mảng tra cứu với tất cả những giá trị ban sơ là NIL. Bất kể khi nào tất cả chúng ta cần giải pháp cho một bài toán con, trước tiên tất cả chúng ta nhìn vào bảng tra cứu. Nếu giá trị được tính toán trước ở đó thì tất cả chúng ta trả về giá trị đó, nếu không, tất cả chúng ta tính toán giá trị và đưa kết quả vào bảng tra cứu để sở hữu thể sử dụng lại sau này.

/* Java program for Memoized version */ public class Fibonacci { final int MAX = 100; final int NIL = -1; int lookup[] = new int[MAX]; /* Function to initialize NIL values in lookup table */ void _initialize() { for (int i = 0; i < MAX; i++) lookup[i] = NIL; } /* function for nth Fibonacci number */ int fib(int n) { if (lookup[n] == NIL) { if (n <= 1) lookup[n] = n; else lookup[n] = fib(n-1) + fib(n-2); } return lookup[n]; } public static void main(String[] args) { Fibonacci f = new Fibonacci(); int n = 40; f._initialize(); System.out.println(“Fibonacci number is” + ” ” + f.fib(n)); } } // This Code is Contributed by Saket Kumar

Tabulation

Tabulation lưu trữ các giá trị từ dưới lên trên. Nó yên cầu ít ngân sách hơn vì nó không phải duy trì ánh xạ và lưu trữ tài liệu ở dạng bảng cho từng giá trị. Nó cũng luôn tồn tại thể tính toán các giá trị không cấp thiết. Điều này còn có thể được sử dụng nếu tất cả những gì bạn muốn là tính toán tất cả những giá trị cho vấn đề của bạn.

Với cách tiếp cận Tabulation, tất cả chúng ta có thể loại bỏ nhu cầu đệ quy và chỉ có trả về kết quả bằng phương pháp lặp qua các thành phần.

/* Java program for Tabulated version */ public class Fibonacci { int fib(int n) { int f[] = new int[n+1]; f[0] = 0; f[1] = 1; for (int i = 2; i <= n; i++) f[i] = f[i-1] + f[i-2]; return f[n]; } public static void main(String[] args) { Fibonacci f = new Fibonacci(); int n = 9; System.out.println(“Fibonacci number is” + ” ” + f.fib(n)); } } // This Code is Contributed by Saket Kumar

Tham khảo

https://www.geeksforgeeks.org/overlapping-subproblems-property-in-dynamic-programming-dp-1/

https://medium.freecodecamp.org/an-intro-to-algorithms-dynamic-programming-dd00873362bb