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

Bạn đang xem: Dynamic programming là gì

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

Đi sâu vào xây dựng động

Tóm lại, bạn cũng có thể nói rằng lập trình đụng được sử dụng đa phần để tối ưu hóa những vấn đề, vào đó họ muốn tìm ra cách tốt nhất để làm một điều gì đó.

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

Các việc con ông xã chéoCấu trúc tối ưu

Trong bài viết này, bọn họ sẽ bàn bạc chi tiết về nằm trong tính thứ nhất (Các bài toán con ck chéo) một phương pháp chi tiết.

Một kịch bản cụ thể như những bài toán con xảy ra lần lượt có các bài toán con nhỏ tuổi hơn của riêng biệt chúng. Cầm cố vì giải quyết việc lặp lại của các bài toán con, thiết kế động xử lý mỗi việc con nhỏ tuổi hơn một lần duy nhất. Sau đó, bạn ghi lại các hiệu quả trong một bảng cơ mà từ đó rất có thể thu được phương án cho vấn đề ban đầu.

Chẳng hạn, những số Fibonacci 0, 1, 1, 2, 3, 5 ,8, 13, gồm một tế bào tả đơn giản dễ dàng trong kia mỗi term có tương quan đến hai term trước nó. Nếu như F(n) là term trang bị n của dãy thì ta có F(n) = F(n - 1) + F(n - 2). Đây được call là bí quyết đệ quy hay quan hệ giới tính lặp lại. Nó cần những term trước này đã được đo lường để thống kê giám sát một term sau.

Các việc con chồng chéo

Lập trình động chủ yếu được áp dụng khi các chiến thuật của cùng một việc con được yêu cầu lặp đi lặp lại. Trong lập trình sẵn động, các chiến thuật được đo lường cho các bài toán nhỏ được tàng trữ trong một bảng để việc thống kê giám sát không phải lặp lại. Vì chưng vậy, lập trình cồn không hữu dụng khi không có các câu hỏi con (chồng chéo) chung vì không tồn tại điểm tàng trữ các giải pháp nếu chúng không cần thiết nữa.

Cách tiếp cận nhằm giải quyết: top-down vs bottom-up

Có nhị cách không giống nhau chính sau đây để xử lý vấn đề:

Top-down: Bạn ban đầu từ trên xuống, giải quyết và xử lý vấn đề lần lượt. Nếu bạn thấy rằng vụ việc đã được giải quyết, thì chỉ cần trả lại câu vấn đáp đã lưu. Điều này được hotline là Memoization.

Bottom-up: chúng ta trực tiếp ban đầu giải những bài toán con nhỏ tuổi hơn nhằm tiến lên đỉnh để tìm ra giải pháp cuối cùng mang lại một vụ việc lớn đó. Trong quy trình này, bảo đảm an toàn rằng các bài toán nhỏ được giải quyết và xử lý trước khi giải quyết vấn đề. Điều này có thể được call là Tabulation

Memoization

Lý do cụ thể cho thuật toán đệ quy bị chậm là bởi nó giám sát các số Fibonacci giống như nhau nhiều lần.

*

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 những cuộc call đệ quy. Sau đó chúng ta cũng có thể tìm kiếm chúng một lần tiếp nữa nếu bọn họ cần chúng sau này.

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

Chúng ta khởi tạo ra một mảng tra cứu giúp với tất cả các giá trị ban sơ là NIL. Bất cứ khi nào chúng ta cần phương án cho một bài toán con, trước tiên chúng ta nhìn vào bảng tra cứu. Nếu quý giá được giám sát trước ở đó thì chúng ta trả về giá trị đó, giả dụ không, bọn họ tính toán quý giá và đưa hiệu quả vào bảng tra cứu để hoàn toàn có 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; /* Function lớn initialize NIL values in lookup table */ void _initialize() { for (int i = 0; i

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 bởi nó không phải gia hạn ánh xạ và lưu trữ dữ liệu ở dạng bảng cho mỗi giá trị. Nó cũng rất có thể tính toán những giá trị không cần thiết. Điều này hoàn toàn có thể được sử dụng nếu tất cả những gì bạn có nhu cầu là đo lường và thống kê tất cả các giá trị cho vấn đề của bạn.

Xem thêm: Chứng Minh Rằng Nhân Dân Việt Nam Từ Xưa Đến Nay Luôn Luôn Sống Theo Đạo Lí Uống Nước Nhớ Nguồn

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

/* Java program for Tabulated version */public class Fibonacci { int fib(int n) { int f<> = new int; f<0> = 0; f<1> = 1; for (int i = 2; i

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