lập trình động và sử dụng ma trận

Question

Tôi luôn nhầm lẫn về cách lập trình động sử dụng ma trận để giải quyết vấn đề. Tôi hiểu rằng ma trận được sử dụng để lưu trữ các kết quả từ các bài toán con trước đó, để nó có thể được sử dụng trong việc tính toán sau này của một vấn đề lớn hơn.

Nhưng, làm cách nào để xác định thứ nguyên của ma trận và cách chúng ta biết giá trị mỗi hàng/cột của ma trận sẽ đại diện như thế nào? tức là, có giống như một thủ tục chung của việc xây dựng ma trận? Ví dụ: nếu chúng tôi quan tâm đến việc thực hiện thay đổi cho số tiền S bằng tiền xu có giá trị c1, c2, .... cn, kích thước của ma trận là gì và mỗi cột/hàng nên là gì? đại diện?

Bất kỳ hướng dẫn định hướng nào cũng sẽ hữu ích. Cảm ơn bạn!

Answer 1

bước Rough đối với một số loại vấn đề DP:

1. Tìm giải pháp đệ quy

2. Nếu một số kết quả trung gian của các cuộc gọi đệ quy được tính một lần nữa và một lần nữa - nhớ họ và sử dụng - xây dựng một bảng với kích thước thích hợp - đó là ghi nhớ

3. Bảng này thường có thể được điền từ ô bắt đầu đến cuối cùng (kết quả) - ô theo ô, từng hàng và cứ ...

Đối với vấn đề thay đổi:

1. F (s) = F (s-c1) + F (s-c2) + ...

Cố gắng xây dựng đầy đủ giải pháp đệ quy và xác định cần có bảng nào để lưu trữ các kết quả trung gian

Answer 2

Một mảng được sử dụng bởi giải pháp DP hầu như luôn dựa trên kích thước của không gian trạng thái của vấn đề - tức là giá trị hợp lệ cho mỗi tham số của nó

Ví dụ

fib[i+2] = fib[i+1] + fib[i] 

là giống như

def fib(i): 
    return fib(i-1)+fib(i-2] 

Bạn có thể làm cho điều này rõ ràng hơn bằng cách thực hiện memoization trong các chức năng đệ quy của bạn

def fib(i): 
    if(memo[i] == null) 
     memo[i] = fib(i-1)+fib(i-2) 
    return memo[i] 

Nếu hàm đệ quy của bạn có các thông số K, bạn có thể sẽ cần một ma trận K-chiều.

Answer 3

Chương này giải thích rất rõ: http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf Ở trang 178, nó cung cấp một số cách tiếp cận để xác định các vấn đề phụ cho phép bạn áp dụng lập trình động.