Hiểu Lập Trình Động Để Bạn Có Thể Sử Dụng Hiệu Quả

Bài viết này không liên quan đến phát triển sản xuất nhưng liên quan đến lập trình. Tôi sẽ thảo luận về Lập trình động (DP) và cách sử dụng kinh nghiệm tính toán trước đó một cách hiệu quả. Tôi hy vọng bạn sẽ thấy nó thú vị.

Giới thiệu về lập trình động

Thuật ngữ Lập trình động lần đầu tiên được sử dụng bởi nhà toán học nổi tiếng người Mỹ, một trong những chuyên gia hàng đầu về công nghệ máy tính, Richard Bellman, vào những năm 1950. Lập trình động (DP) là một phương pháp giải quyết các nhiệm vụ phức tạp bằng cách chia chúng thành các vấn đề nhỏ hơn.

Loại vấn đề mà DP có thể giải quyết phải đáp ứng hai tiêu chí:

1. Cấu trúc nền tối ưu . Lập trình động có nghĩa là lời giải của các bài toán con nhỏ hơn có thể được sử dụng để giải bài toán ban đầu. Cấu trúc con tối ưu là đặc điểm chính của mô hình “Chia để trị”.

Một ví dụ cổ điển về việc triển khai là thuật toán sắp xếp hợp nhất, trong đó chúng tôi chia bài toán theo cách đệ quy thành các bài toán con đơn giản nhất (mảng có kích thước 1), sau đó chúng tôi thực hiện các phép tính dựa trên từng bài toán. Các kết quả được sử dụng để giải quyết lớp tiếp theo (các vấn đề phụ lớn hơn) cho đến khi đạt được lớp ban đầu.

2. Các vấn đề phụ chồng chéo . Trong khoa học máy tính, một bài toán được cho là có các bài toán con chồng chéo nếu bài toán đó có thể được chia thành các bài toán con được sử dụng lại nhiều lần. Nói cách khác, chạy cùng một mã với cùng dữ liệu đầu vào và cho kết quả giống nhau. Một ví dụ kinh điển của vấn đề này là phép tính phần tử thứ N trong dãy Fibonacci mà chúng ta sẽ xem xét bên dưới.

Bạn có thể nói rằng DP là một trường hợp đặc biệt của việc sử dụng mô hình Phân chia để Chinh phục hoặc một phiên bản phức tạp hơn của nó. Mẫu này rất phù hợp để giải quyết các nhiệm vụ liên quan đến tổ hợp, trong đó tính toán một số lượng lớn các kết hợp khác nhau, nhưng số lượng N phần tử thường đơn điệu và giống hệt nhau.

Trong các bài toán về cấu trúc con tối ưu và các bài toán con chồng chéo, chúng ta có rất nhiều phép tính và phép toán lặp lại nếu chúng ta áp dụng cách tiếp cận vũ phu. DP giúp chúng tôi tối ưu hóa giải pháp và tránh việc tính toán gấp đôi bằng cách sử dụng hai phương pháp chính: ghi nhớ và lập bảng:

1. Việc ghi nhớ (cách tiếp cận từ trên xuống) được thực hiện thông qua đệ quy. Một nhiệm vụ được chia thành các vấn đề phụ nhỏ hơn, kết quả của chúng được đưa vào bộ nhớ và kết hợp lại để giải quyết vấn đề ban đầu thông qua việc sử dụng nhiều lần.

• Nhược điểm: Cách tiếp cận này sử dụng bộ nhớ ngăn xếp thông qua các lệnh gọi phương thức đệ quy
• Ưu điểm: Tính linh hoạt đối với các nhiệm vụ DP.

2. Việc lập bảng (cách tiếp cận từ dưới lên) được thực hiện bằng phương pháp lặp. Các bài toán con từ nhỏ nhất đến ban đầu được tính toán tuần tự, lặp đi lặp lại.

• Nhược điểm: phạm vi ứng dụng hạn chế. Cách tiếp cận này đòi hỏi sự hiểu biết ban đầu về toàn bộ chuỗi các vấn đề phụ. Nhưng trong một số vấn đề, điều này là không khả thi.
• Ưu điểm: sử dụng bộ nhớ hiệu quả vì mọi thứ đều chạy trong một chức năng duy nhất.

Lý thuyết này nghe có vẻ tẻ nhạt và khó hiểu - hãy xem một số ví dụ.

Vấn đề: Dãy số Fibonacci

Một ví dụ cổ điển về DP là tính toán phần tử thứ N trong dãy Fibonacci, trong đó mỗi phần tử là tổng của hai phần tử trước đó và phần tử thứ nhất và thứ hai bằng 0 và 1.

Theo giả thuyết, ban đầu chúng ta tập trung vào bản chất của cấu trúc con tối ưu, vì để tính một giá trị, chúng ta cần tìm giá trị trước đó. Để tính giá trị trước đó, chúng ta cần tìm giá trị đứng trước đó, v.v. Bản chất của các nhiệm vụ phụ chồng chéo được minh họa trong sơ đồ bên dưới.

Đối với nhiệm vụ này, chúng ta sẽ xem xét ba trường hợp:

1. Cách tiếp cận đơn giản: nhược điểm là gì?
2. Một giải pháp tối ưu hóa sử dụng tính năng ghi nhớ
3. Một giải pháp tối ưu hóa bằng cách sử dụng bảng

Cách tiếp cận đơn giản/tàn bạo

Điều đầu tiên bạn có thể nghĩ đến là nhập đệ quy, tính tổng hai phần tử trước đó và đưa ra kết quả của chúng.

 /** * Straightforward(Brute force) approach */ fun fibBruteForce(n: Int): Int { return when (n) { 1 -> 0 2 -> 1 else -> fibBruteForce(n - 1) + fibBruteForce(n - 2) } }

Trên màn hình bên dưới, bạn có thể thấy một loạt lệnh gọi hàm để tính phần tử thứ năm trong chuỗi.

Lưu ý rằng hàm fib(1) được gọi năm lần và fib(2) gọi ba lần. Các hàm có một chữ ký, có cùng tham số, được khởi chạy lặp lại và thực hiện cùng một việc. Khi số N tăng lên, cây tăng lên, không phải tuyến tính mà theo cấp số nhân, dẫn đến sự trùng lặp khổng lồ của các phép tính.

Phân tích toán học:

Độ phức tạp thời gian: O(2n),

Độ phức tạp của không gian: O(n) -> tỷ lệ thuận với độ sâu tối đa của cây đệ quy, vì đây là số phần tử tối đa có thể có trong ngăn xếp các lệnh gọi hàm ẩn.

Kết quả: Cách tiếp cận này cực kỳ kém hiệu quả. Ví dụ: cần 1.073.741.824 thao tác để tính phần tử thứ 30.

Ghi nhớ (Phương pháp tiếp cận từ trên xuống)

Theo cách tiếp cận này, việc triển khai không khác mấy so với giải pháp “bạo lực” nói trên, ngoại trừ việc phân bổ bộ nhớ. Đặt nó là một bản ghi nhớ có thể thay đổi, trong đó chúng tôi thu thập kết quả tính toán của bất kỳ hàm fib() đã hoàn thành nào trong ngăn xếp của chúng tôi.

Cần lưu ý rằng chỉ cần có một mảng các số nguyên và tham chiếu nó theo chỉ mục là đủ, nhưng, để rõ ràng về mặt khái niệm, một bản đồ băm đã được tạo ra.

 /** * Memoization(Top-down) approach */ val memo = HashMap<Int, Int>().apply { this[1] = 0 this[2] = 1 } fun fibMemo(n: Int): Int { if (!memo.containsKey(n)) { val result = fibMemo(n - 1) + fibMemo(n - 2) memo[n] = result } return memo[n]!! }

Hãy tập trung lại vào ngăn xếp lệnh gọi hàm:

• Hàm hoàn thành đầu tiên ghi kết quả vào bản ghi nhớ là fib(2) được tô sáng. Nó trả lại quyền điều khiển cho fib(3) được đánh dấu.
• fib(3) được đánh dấu sẽ tìm thấy giá trị của nó sau khi tổng hợp kết quả của các lệnh gọi fib(2) và fib(1) , nhập giải pháp của nó vào bản ghi nhớ và trả lại quyền điều khiển cho fib(4) .
• Chúng ta đã đạt đến giai đoạn sử dụng lại trải nghiệm trước đó - khi quyền điều khiển được trả về fib(4) , lệnh gọi fib(2) đang chờ đến lượt nó. fib(2) lần lượt, thay vì gọi ( fib(1) + fib(0) ), sử dụng toàn bộ giải pháp đã hoàn thành từ bản ghi nhớ và trả lại ngay lập tức.
• fib(4) được tính toán và trả lại quyền kiểm soát cho fib(5) , chỉ phải khởi chạy fib(3) . Trong phép tương tự cuối cùng, fib(3) ngay lập tức trả về một giá trị từ bản ghi nhớ mà không cần tính toán.

Chúng ta có thể quan sát thấy số lượng lệnh gọi hàm và tính toán giảm đi. Ngoài ra, khi N tăng lên thì số lần giảm sẽ ít hơn theo cấp số nhân.

Phân tích toán học:

Độ phức tạp thời gian: O(n)

Độ phức tạp của không gian: O(n)

Kết quả: Có sự khác biệt rõ ràng về độ phức tạp tiệm cận. Cách tiếp cận này đã làm giảm nó thành tuyến tính theo thời gian, so với giải pháp nguyên thủy và không tăng nó trong bộ nhớ.

Lập bảng (cách tiếp cận từ dưới lên)

Như đã đề cập ở trên, cách tiếp cận này liên quan đến việc tính toán lặp lại từ bài toán con nhỏ hơn đến bài toán con lớn hơn. Trong trường hợp của Fibonacci, “bài toán con” nhỏ nhất lần lượt là phần tử thứ nhất và thứ hai trong chuỗi, 0 và 1.

Chúng ta biết rõ các phần tử có liên hệ với nhau như thế nào, được thể hiện trong công thức: fib(n) = fib(n-1) + fib(n-2) . Bởi vì chúng ta biết các yếu tố trước nên chúng ta có thể dễ dàng tính ra yếu tố tiếp theo, yếu tố sau đó, v.v.

Bằng cách tổng hợp các giá trị mà chúng tôi biết, chúng tôi có thể tìm thấy phần tử tiếp theo. Chúng tôi thực hiện thao tác này theo chu kỳ cho đến khi tìm thấy giá trị mong muốn.

 /** * Tabulation(Bottom-up) approach fun fibTab(n: Int): Int { var element = 0 var nextElement = 1 for (i in 2 until n) { val newNext = element + nextElement element = nextElement nextElement = newNext } return nextElement }

Phân tích toán học:

Độ phức tạp thời gian: O(n)

Độ phức tạp của không gian: O(1)

Kết quả: Cách tiếp cận này cũng hiệu quả như việc ghi nhớ về mặt tốc độ, nhưng nó sử dụng một lượng bộ nhớ không đổi.

Vấn đề: Cây nhị phân duy nhất

Hãy xem xét một vấn đề phức tạp hơn: chúng ta cần tìm số lượng tất cả các cây nhị phân có cấu trúc duy nhất có thể được tạo từ N nút.

Cây nhị phân là một cấu trúc dữ liệu có thứ bậc, trong đó mỗi nút có không quá hai nút con. Theo nguyên tắc chung, nút đầu tiên được gọi là nút cha và có hai con - con trái và con phải.

Giả sử rằng chúng ta cần tìm giải pháp cho N = 3. Có 5 cây có cấu trúc duy nhất cho ba nút. Chúng ta có thể đếm chúng trong đầu, nhưng nếu N tăng lên, các biến thể sẽ tăng lên rất nhiều và việc hình dung chúng trong đầu là không thể.

Nhiệm vụ này có thể được gán cho tổ hợp. Hãy cùng tìm hiểu xem những sự kết hợp nào có thể được hình thành và cách chúng ta có thể tìm ra mô hình cho sự hình thành của chúng.

1. Mỗi cây bắt đầu từ nút trên cùng (Đỉnh của cây). Cây sau đó mở rộng theo chiều sâu.
2. Mỗi nút là điểm bắt đầu của một cây con mới (cây con), như được hiển thị trên màn hình. Cây con bên trái có màu xanh lá cây và cây con bên phải có màu đỏ. Mỗi cái có một đỉnh riêng.

Hãy xem một ví dụ về một nhiệm vụ, trong đó N = 6 ở cấp độ khái niệm. Chúng ta sẽ gọi hàm tính toán của mình là numOfUniqueTrees(n: Int) .

Trong ví dụ của chúng tôi, 6 nút được đưa ra, một trong số đó, theo nguyên tắc đã đề cập trước đó, tạo thành đỉnh của cây và 5 nút còn lại - phần còn lại.

Từ giờ trở đi, chúng tôi tương tác với các nút còn lại. Điều này có thể được thực hiện theo nhiều cách khác nhau. Ví dụ: bằng cách sử dụng tất cả năm nút để tạo thành cây con bên trái hoặc gửi tất cả năm nút đến cây con bên phải. Hoặc bằng cách chia các nút thành hai - 2 ở bên trái và 3 ở bên phải (xem màn hình bên dưới), chúng ta có một số lượng hạn chế các biến thể như vậy.

Để đạt được kết quả numOfUniqueTrees(6) , chúng ta cần xem xét tất cả các biến thể để phân phối các nút của mình. Chúng được thể hiện trong bảng:

Bảng hiển thị 6 phân phối khác nhau của các nút. Nếu chúng tôi tìm thấy có thể tạo ra bao nhiêu cây duy nhất cho mỗi lần phân phối và tổng hợp chúng lại, chúng tôi sẽ đạt được kết quả cuối cùng.

Làm thế nào để tìm số lượng cây duy nhất để phân phối?

Chúng ta có 2 tham số: Left Nodes và Right Nodes (cột trái và phải trong bảng).

Kết quả sẽ bằng: numOfUniqueTrees(leftNodes) * numOfUniqueTrees(rightNodes) .

Tại sao? Ở bên trái, chúng ta sẽ có X cây duy nhất và với mỗi cây, chúng ta có thể đặt Y biến thể duy nhất của cây ở bên phải. Chúng tôi nhân những điều này để có được kết quả.

Vì vậy, hãy tìm hiểu các biến thể cho phân phối đầu tiên (5 trái, 0 phải)

numOfUniqueTrees(5) * numOfUniqueTrees(0) , vì chúng tôi không có nút nào ở bên phải. Kết quả là numOfUniqueTrees(5) — số lượng cây con duy nhất ở bên trái có giá trị bên phải không đổi.

Đang tính numOfUniqueTrees(5) .

Bây giờ chúng ta có bài toán con nhỏ nhất. Chúng ta sẽ thao tác với nó giống như chúng ta đã làm với cái lớn hơn. Ở giai đoạn này, đặc điểm của nhiệm vụ DP rất rõ ràng - cấu trúc con tối ưu, hành vi đệ quy.

Một nút (nút màu xanh lá cây) được gửi đến đỉnh. Chúng tôi phân phối (bốn) nút còn lại theo cách tương tự với trải nghiệm trước đó (4:0), (3:1), (2:2), (1:3), (0:4).

Chúng tôi tính toán phân phối đầu tiên (4:0). Nó bằng numOfUniqueTrees(4) * numOfUniqueTrees(0) -> numOfUniqueTrees(4) theo cách tương tự trước đó.

Đang tính numOfUniqueTrees(4) . Nếu chúng ta phân bổ một nút cho đỉnh thì chúng ta còn lại 3 nút.

Phân phối (3:0), (2:1), (1:2), (0:3).

Đối với 2 nút chỉ có hai cây nhị phân duy nhất, đối với 1 — một. Trước đây chúng tôi đã đề cập rằng có 5 biến thể của cây nhị phân duy nhất cho ba nút.

Kết quả là — phân phối (3:0), (0:3) bằng 5, (2:1), (1:2) — 2. Nếu chúng ta cộng 5 + 2 + 2 + 5, chúng ta nhận được 14 numOfUniqueTrees(4) = 14.

Hãy nhập kết quả phép tính vào biến memo theo kinh nghiệm ghi nhớ. Bất cứ khi nào chúng tôi cần tìm các biến thể cho bốn nút, chúng tôi sẽ không tính toán lại chúng mà sử dụng lại kinh nghiệm trước đó.

Hãy quay lại phép tính (5:0), bằng tổng của các phân bố (4:0), (3:1), (2:2), (1:3), (0:4). Chúng ta biết rằng (4:0) = 14. Hãy quay lại bản ghi nhớ, (3:1) = 5, (2:2) = 4 (2 biến thể ở bên trái * 2 ở bên phải), (1:3) = 5, (0:4) = 14. Nếu cộng chúng lại, chúng ta sẽ có 42, numOfUniqueTrees(5) = 42.

Hãy quay lại phép tính numOfUniqueTrees(6) , bằng tổng của các phân phối.

(5:0) = 42, (4:1) = 14, (3:2) =10 (5 trái * 2 phải), (2:3) = 10, (1:4) = 14, (0: 5) = 42. Nếu cộng chúng lại, chúng ta sẽ nhận được 132, numOfUniqueTrees(5) = 132 .

Nhiệm vụ đã được giải quyết!

Kết quả: Hãy lưu ý các bài toán con chồng chéo trong lời giải có N = 6. Trong lời giải đơn giản, numOfUniqueTrees(3) sẽ được gọi 18 lần (màn hình bên dưới). Với việc tăng N, số lần lặp lại tính toán tương tự sẽ lớn hơn nhiều.

Tôi nhấn mạnh rằng số lượng cây duy nhất cho (5 trái, 0 phải) và (0 trái, 5 phải) sẽ giống nhau. Chỉ trong một trường hợp, chúng sẽ ở bên trái và trong trường hợp khác ở bên phải. Điều này cũng áp dụng cho (4 trái, 1 phải) và (1 trái, 4 phải).

Ghi nhớ, như một cách tiếp cận của lập trình động, đã cho phép chúng tôi tối ưu hóa giải pháp cho một nhiệm vụ phức tạp như vậy.

Thực hiện

 class Solution { fun calculateTees(n: Int, memo:Array<Int?>): Int { var treesNum = 0 if(n < 1) return 0 if(n == 2) return 2 if(n == 1) return 1 if(memo[n]!=null) return memo[n]!! for (i in 1..n){ val leftSubTrees = calculateTees( i - 1, memo) val rightSubTrees = calculateTees(n - i, memo) treesNum += if(leftSubTrees>0 && rightSubTrees>0){ leftSubTrees*rightSubTrees } else leftSubTrees+leftSubTrees } memo[n] = treesNum return treesNum } } 

Phần kết luận

Trong một số trường hợp, việc giải quyết các nhiệm vụ bằng Lập trình động có thể tiết kiệm rất nhiều thời gian và giúp thuật toán hoạt động với hiệu quả tối đa.

Cảm ơn bạn đã đọc bài viết này đến cuối. Tôi rất vui được trả lời câu hỏi của bạn.