DP part 5 - Last version

II.5 Kho báu kia kìa

Bài toán: Cho bản đồ n*m (n, m <=1000). Ô i,j có giá trị là a(i,j)
Ta sẽ xuất phát từ 1 ô bất kì ở cột 1 đến 1 ô bất kì ở cột n . Chi phí đường đi sẽ là tổng giá trị các ô. Ta cần tính đường đi với chi phí nhỏ nhất.
Từ (i,j) --> (i+1,j) hoặc (i,j+1)

VD: Với hình 3*3

1 2 3

4 5 6

7 8 9

Ta có 1 đường đi là (1,1) --> (1,2) --> (2,2) --> (2,3) với tổng chi phí : 1 + 2 + 5 + 6 = 14 . Tuy nhiên ta có 1  đường đi có chi phí nhỏ nhất là (1.1) --(1,2) -- (1,3)  với tổng chi phí là 1+2+3 = 6.

Công thức qhđ : F[i][j] --> là chi phí nhỏ nhất để đi đến ô (i,j)
Rõ ràng có thể đến được ô (i,j) là (i,j-1) hoặc (i-1,j) (ngay sau 1 bước)
Do đó ta có 1 ct qhđ khá hồn nhiên F[i][j] = min (F[i-1][j] , F[i][j-1]) + a[i][j] .
Độ phức tạp là O(n*m)

II.6 Nhiều thông tin hơn nữa
Với những mục trên , mình đã trình bày 1 số ý tưởng cơ bản nhất của quy hoạch động . Tuy nhiên , bài viết của mình chỉ mang tính chủ quan nên sẽ mắc 1 vài sai sót mong các bạn thông cảm và góp ý với mình tại email : aloneranger97@gmail.com
Để sửa chữa những"lỗi lầm" mình sẽ post một vài link hữu ích cho những bạn mới học quy hoạch động
+  http://cntt.epu.edu.vn/images/book_LeMinhHoang.pdf -- Đây được coi là quyển sách huyền thoại cho newbin lập trình ở Việt Nam của thầy Lê Minh Hoàng
+ http://codeforces.com/problemset/tags/dp  - đây là link để các bạn traing các kĩ năng của mình.
+ https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/
http://vnoi.info/wiki/Home  - cùng nhau ủng hộ nào

+ Nếu xa hơn, quy hoạch động còn có thể áp dụng với nhiều cộng cụ khác khá là fun :) ví dụ như IT, BIT, chặt nhị phần .. Và bạn sẽ thấy Tin học rất lí thú , Hãy hưởng thụ và cảm nhận sự lí thú của tin học nhé :)