Please or Register to create posts and topics.

Thuật toán quy hoạch động

Thuật toán quy hoạch động

  • Nguồn: Topcoder.

    Có rất nhiều bài toán được áp dụng quy hoạch động (QHĐ) (Dynamic Programming). QHĐ là một trong những kĩ thuật quan trọng. Bài viết này sẽ giúp bạn hiểu được QHĐ thông qua các ví dụ cụ thể.

    Note: Trong bài này có thể có nhiều phần bạn đã biết, bạn hoàn toàn có thể chuyển qua đọc phần khác.

    Beginner

    QHĐ là gì ?

    QHĐ là kĩ thuật được được dùng khi có một công thức và một (hoặc một vài) trạng thái bắt đầu. Một bài toán được tính bởi các bài toán nhỏ hơn đã tìm ra trước đó. QHĐ có độ phức tạp đa thức nên sẽ chạy nhanh hơn quay lui và duyệt trâu.

    Để hiểu rõ hơn hãy xem ví dụ sau:

    Cho <span id="MathJax-Element-1-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN đồng xu và giá tiền của mỗi đồng (<span id="MathJax-Element-2-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="V0,V1,…,VN−1 ">V0,V1,,VN1 V0,V1,…,VN−1 ), và số <span id="MathJax-Element-3-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S">SS. Tìm số đồng xu nhỏ nhất để tổng giá trị của chúng bằng <span id="MathJax-Element-4-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S">SS (số lượng đồng xu không giới hạn).

    Bây giờ chúng ta sẽ xây dựng thuật giải:

    Đầu tiên, cần tìm một trạng thái của bài toán.

    Trạng thái là gì ?

    Trạng thái là một trường hợp, một bài toán con của bài toán lớn.

    Ví dụ, trạng thái trong bài này là số lượng xu nhỏ nhất để tổng bằng <span id="MathJax-Element-5-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="i">ii, với <span id="MathJax-Element-6-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="i≤S">iSi≤S. Để tìm ra trạng thái <span id="MathJax-Element-7-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="i">ii, cần phải tìm tất cả các trạng thái <span id="MathJax-Element-8-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="j">jj mà <span id="MathJax-Element-9-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="(j&lt;i)">(j<i)(j<i). Một khi đã tìm ra trạng thái <span id="MathJax-Element-10-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="i">ii, ta có thể dễ dàng tìm ra trạng thái của <span id="MathJax-Element-11-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="i+1">i+1i+1.

    Làm thế nào để tìm được ?

    Với mỗi <span id="MathJax-Element-12-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="j">jj, <span id="MathJax-Element-13-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Vj≤i">VjiVj≤i, tìm số đồng xu nhỏ nhất để tổng bằng <span id="MathJax-Element-14-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="i−Vj">iVji−Vj. Giả sử nó bằng <span id="MathJax-Element-15-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="m">mm. Nếu <span id="MathJax-Element-16-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="m+1">m+1m+1 nhỏ hơn số lượng đồng xu hiện tại cho tổng <span id="MathJax-Element-17-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="i">ii thì ta cập nhập nó bằng <span id="MathJax-Element-18-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="m+1">m+1m+1.

    Sau đây là ví dụ: Cho các đồng xu với giá tiền 1, 3 và 5. Và <span id="MathJax-Element-19-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S">SS = 11.

    Đầu tiên, ta bắt đầu từ trạng thái 0, chúng ta có <span id="MathJax-Element-20-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="f[0]=0">f[0]=0f[0]=0. Xét đến tổng 1. Có duy nhất đồng xu 1 nhỏ hơn hoặc bằng tổng 1, nên ta có <span id="MathJax-Element-21-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="f[1]=f[1−V0]+1=f[0]+1=1">f[1]=f[1V0]+1=f[0]+1=1f[1]=f[1−V0]+1=f[0]+1=1. Xét đến tổng 2. Cũng giống như tổng trước, chỉ có 1 đổng xu <span id="MathJax-Element-22-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="≤"> 2, có <span id="MathJax-Element-23-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="f[2]=f[2−V0]+1=f[1]+1=2">f[2]=f[2V0]+1=f[1]+1=2f[2]=f[2−V0]+1=f[1]+1=2 Đến tổng 3. Lần này có 2 đồng xu <span id="MathJax-Element-24-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="≤"> 3 là 1 và 3. - Nếu ta chọn đồng 1, ta có <span id="MathJax-Element-25-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="f[3]=f[3−V0]+1=f[2]+1=3">f[3]=f[3V0]+1=f[2]+1=3f[3]=f[3−V0]+1=f[2]+1=3 - Nếu ta chọn đồng 3, ta có <span id="MathJax-Element-26-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="f[3]=f[3−V1]+1=f[0]+1=1">f[3]=f[3V1]+1=f[0]+1=1f[3]=f[3−V1]+1=f[0]+1=1 Rõ ràng là 1 <span id="MathJax-Element-27-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="≤"> 3 nên ta chọn đồng 3 và <span id="MathJax-Element-28-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="f[3]=1">f[3]=1f[3]=1 Xét tiếp đến tổng 4, rồi đến 11 bằng cách như trên.

    Mã giả:

    Gán Min[i] bằng dương vô cùng với mọi i
    Min[0]=0
    
    For i = 1 to S
    For j = 0 to N - 1
       If (Vj<=i AND Min[i-Vj]+1<Min[i])
    Then Min[i]=Min[i-Vj]+1
    Output Min[S]
    

    Đây là lời giải cho tất cả các tổng:

    Tổng Lượng xu nhỏ nhất Xu được chọn
    (tổng còn lại)
    0 0 -
    1 1 1 (0)
    2 2 1 (1)
    3 1 3 (0)
    4 2 1 (3)
    5 1 5 (0)
    6 2 3 (3)
    7 3 1 (6)
    8 2 3 (5)
    9 3 1 (8)
    10 2 5 (5)
    11 3 1 (10)

    Vậy là chúng ta đã tìm được lời giải cho 3 đồng xu tổng bằng 11. Dựa vào bảng trên, ta có thể truy vết lại được những đồng xu nào được chọn để tối ưu bài toán. Bài QHĐ trên còn có một cách tiếp cận khác nữa. Lần này, ta sẽ không tính liên tiếp các tổng. Bắt đầu từ trạng thái 0. Thử nhét đồng xu thứ 1 vào các tổng đã tính. Nếu như tổng <span id="MathJax-Element-29-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="t">tt có số đồng xu ít hơn số đồng xu hiện tại thì tiến hành cập nhật. Rồi tiếp tục thử với đồng thứ 2, 3 cho đến khi thử hết các đồng. Ví dụ, nhét đồng 1 (giá trị 1) vào tổng 0 ta có tổng 1. Vì ta chưa tính tổng 1 nên <span id="MathJax-Element-30-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S[1]=1">S[1]=1S[1]=1. Nhét đồng 1 vào tổng 1 ta có <span id="MathJax-Element-31-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S[2]=2">S[2]=2S[2]=2. Tiếp tục làm như vậy với các tổng còn lại. Sau đồng 1, ta nhét đồng 2(giá trị 3) vào tổng 0 ta được 1, mà <span id="MathJax-Element-32-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S[3]=3&gt;1">S[3]=3>1S[3]=3>1, ta cập nhật <span id="MathJax-Element-33-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S[3]=1">S[3]=1S[3]=1. Tiếp tục nhét đồng 2 vào các tổng còn lại, cũng nhứ thử nhét các đồng xu khác.

    #Elementary

    Bây giờ, chúng ta cùng đến một khái niệm mới, công thức truy hồi (recurrent relation), mối liên hệ giữa những trạng thái.

    Ví dụ: Cho một dãy N số - <span id="MathJax-Element-34-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="A[1],A[2],…,A[N]">A[1],A[2],,A[N]A[1],A[2],…,A[N]. Tìm dãy con không giảm dài nhất.

    Ta quy định trạng thái <span id="MathJax-Element-35-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S[i]">S[i]S[i] là dãy con không giảm dài nhất kết thúc tại <span id="MathJax-Element-36-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="A[i]">A[i]A[i]. Với <span id="MathJax-Element-37-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="i&gt;1">i>1i>1 và <span id="MathJax-Element-38-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="j&lt;i">j<ij<i, tính được <span id="MathJax-Element-39-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="i">ii khi tồn tại <span id="MathJax-Element-40-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="A[j]≤A[i]">A[j]A[i]A[j]≤A[i] (vì đây là dãy không giảm). Khi đó <span id="MathJax-Element-41-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S[i]=Max(S[i],S[j]+1)">S[i]=Max(S[i],S[j]+1)S[i]=Max(S[i],S[j]+1). Tiếp tục tính như vậy cho đến khi đến được trạng thái <span id="MathJax-Element-42-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S[N]">S[N]S[N].

    Hãy xem bảng sau với dãy: 5, 3, 4, 8, 6, 7:

    I Độ dài dãy con
    không giảm dài nhất
    của i số đầu tiên
    Vị trí của kí tự cuối
    trong dãy
    1 1 1
    2 1 2
    3 2 2
    4 3 3
    5 3 3
    6 4 5

    Bài luyện tập: Cho đồ thị vô hướng <span id="MathJax-Element-43-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="G">GG có <span id="MathJax-Element-44-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN đỉnh (<span id="MathJax-Element-45-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N≤1000">N1000N≤1000) và các cạnh có trọng số dương. Tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh <span id="MathJax-Element-46-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN hoặc thông báo không tồn tại đường đi. Gợi ý: Tại mỗi bước, chọn ra trong số các đỉnh chưa thăm mà có đường đi từ 1, chọn ra đỉnh có đường đi ngắn nhất.

    Các bài ví dụ khác:

    Intermediate

    Tới đây bạn sẽ được làm quen với QHĐ 2 chiều.

    Bài toán: Cho một bảng <span id="MathJax-Element-47-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="M∗N">MNM∗N, mỗi ô có một lượng táo. Bắt đầu từ ô trái trên, mỗi bước có thể đi sang phải hoặc xuống dưới. Bạn có thể ăn được nhiều nhất bao nhiêu quả táo ?

    Cách giải bài này cũng tương tự như những bài trước.

    Đầu tiên là phải xác định trạng thái là gì. Ở mỗi ô có nhiều nhất 2 cách có thể tới được ô đó, từ ô bên trái và ô phía trên. Do vậy, để tìm trạng thái hiện tại, ta phải tính trước các ô có thể đến được nó.

    Ta có công thức truy hồi sau: <span id="MathJax-Element-48-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S[i][j]=A[i][j]+max(S[i−1][j],if">S[i][j]=A[i][j]+max(S[i1][j],ifS[i][j]=A[i][j]+max(S[i−1][j],if <span id="MathJax-Element-49-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="i&gt;0;S[i][j−1],if">i>0;S[i][j1],ifi>0;S[i][j−1],if <span id="MathJax-Element-50-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="j&gt;0)">j>0)j>0) (trong đó, <span id="MathJax-Element-51-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="i">ii là hàng, <span id="MathJax-Element-52-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="j">jj là cột, <span id="MathJax-Element-53-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="A[i][j]">A[i][j]A[i][j] là số táo ở ô <span id="MathJax-Element-54-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="i,j">i,ji,j) <span id="MathJax-Element-55-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S[i][j]">S[i][j]S[i][j] có thể được tính từ trái sang phải, từ trên xuống dưới, hoặc từ trên xuống, từ trái sang.

    Mã giả:

    For i = 0 to N - 1
       For j = 0 to M - 1
       S[i][j] = A[i][j] +
          max(S[i][j-1], if j>0 ; S[i-1][j], if i>0 ; 0)
    
    Output S[n-1][m-1]
    

    Ví dụ khác:

    #Upper-Intermediate

    Phần này sẽ giới thiệu với bạn những bài toán cùng với một số điều kiện.

    Đây là một ví dụ cụ thể:

    Cho đồ thị vô hướng <span id="MathJax-Element-56-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="G">GG có trọng số dương và <span id="MathJax-Element-57-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN đỉnh.

    Ban đầu bạn có số tiền là <span id="MathJax-Element-58-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="M">MM. Để đi qua đỉnh <span id="MathJax-Element-59-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="i">ii, bạn phải trả số tiền là <span id="MathJax-Element-60-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S[i]">S[i]S[i]. Và đương nhiên, nếu không đủ tiền thì bạn không đi được. Tìm đường đi ngắn nhất từ 1 tới <span id="MathJax-Element-61-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN thỏa mãn tiêu chí trên. Nếu có nhiều đường ngắn nhất, in ra đường với chi phí nhỏ nhất. Giới hạn: <span id="MathJax-Element-62-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="1&lt;N≤100">1<N1001<N≤100; <span id="MathJax-Element-63-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="0≤M≤100">0M1000≤M≤100; <span id="MathJax-Element-64-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="0≤S[i]≤100">0S[i]1000≤S[i]≤100.

    Có thể dễ dàng thấy đây là một bài Dijkstra cơ bản, tuy nhiên chỉ khác ở chỗ nó có thêm một điều kiện. Trong bài toán Dijkstra cơ bản ta có <span id="MathJax-Element-65-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Min[i]">Min[i]Min[i] , là độ dài đường đi ngắn nhất từ 1 tới <span id="MathJax-Element-66-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="i">ii. Còn ở đây, chúng ta cần phải quan tâm đến số tiền còn lại. Do đó chúng ta có thể mở rộng mảng này thành <span id="MathJax-Element-67-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Min[i][j]">Min[i][j]Min[i][j] , là độ dài đường đi ngắn nhất tới <span id="MathJax-Element-68-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="i">ii, và còn lại số tiền là <span id="MathJax-Element-69-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="j">jj. Bằng cách này bài toán đã được đưa về bài toán Dijkstra quen thuộc. Tại mỗi bước ta tìm trạng thái <span id="MathJax-Element-70-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="(i,j)">(i,j)(i,j) có quãng đường ngắn nhất, đánh dấu là đã thăm rồi update cho các trạng thái cạnh nó. Đáp án sẽ là <span id="MathJax-Element-71-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Min[N][j]">Min[N][j]Min[N][j] có giá trị nhỏ nhất (và <span id="MathJax-Element-72-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="j">jj lớn nhất trong số các <span id="MathJax-Element-73-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Min[N][j]">Min[N][j]Min[N][j] có cùng giá trị).

    Mã giả:

    Gán mọi(i,j) là chưa thăm
    Gán Min[i][j] bằng dương vô cùng với mọi (i,j)
    
    Min[0][M]=0
    
    While(TRUE)
    
        Trong số những trạng thái chưa thăm (i,j) tìm cái có Min[i][j]
        nhỏ nhất. Giải sử nó là (k,l).
    
        Nếu không tìm được (k,l) nào mà Min[k][l] nhỏ hơn dương vô cùng - thoát vòng lặp.
    
        Đánh dấu (k,l) đã thăm
    
        For All Neighbors p of Vertex k.
           If (l-S[p]>=0 AND
            Min[p][l-S[p]]>Min[k][l]+Dist[k][p])
              Then Min[p][l-S[p]]=Min[k][l]+Dist[k][p]
           i.e.
        Nếu tại (i,j) có đủ tiền để đi qua p (l-S[p] là số tiền còn lại sau khi đi qua p), và đường đi ngắn nhất của (p,l-S[p]) lớn hơn [đường đi ngắn nhất tới (k,l)] + [khoảng cách từ k tới p)],
        thì gán (i,j) bằn tổng này.
        End For
    
    End While
    
    Tìm số nhỏ nhất trong các Min[N-1][j] (for all j, 0<=j<=M);
    Nếu có nhiều hơn một trạng thái, lấy trạng thái nào có j lớn nhất. Nếu không có (N-1,j) nào nhỏ hơn dương vô cùng - không tồn tại đường đi.
    

    Các bài luyện tập:

    Advanced

    Những bài sau đây sẽ cần một chút kĩ năng phân tích để có thể tối ưu chúng thành bài QHĐ.

    Problem StarAdventure – SRM 208 Div 1:

    Cho ma trận M hàng, N cột (<span id="MathJax-Element-74-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N∗M">NMN∗M). Mỗi ô có một lượng táo. Bạn đang ở ô góc trái trên. Bạn chỉ có thể đi xuống hoặc sang phải. Bạn cần tới ô góc phải dưới. Rồi quay lại ô trái trên bằng cách lên hoặc sang trái. Cuối cùng, bạn quay lại ô phải dưới. Tìm số táo nhiều nhất mà bạn có thể ăn được. Khi đi qua một ô, toàn bộ táo của ô đấy sẽ bị ăn hết.

    Giới hạn: <span id="MathJax-Element-75-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="1&lt;N,M≤50">1<N,M501<N,M≤50 mỗi ô có từ 0 đến 1000 quả táo.

    Đọc đến đây, hẳn bạn sẽ thấy cái đề này quen quen, nó chính là bài mở rộng của bài toán phần Intermediate. Ta có thể thử đưa bài toán này về thành bài toán trên. Để ý thấy đường đi từ ô góc phải dưới lên trái trên cũng có thể coi là một đường đi từ góc trái trên xuống. Như vậy, chúng ta phải xử lý bài toán với 3 đường đi từ trái trên xuống. Gọi 3 đường này là trái, giữa và phải. Khi 2 đường giao nhau (như hình dưới):

    enter image description here

    thì nó cũng tương đương với hình sau:

    enter image description here

    Bằng cách này, chúng ta đã có một cái nhìn khác về bài toán. Các đường này sẽ không giao nhau (trừ ô góc trái trên và phải dưới). Với mỗi hàng y (không phải hàng đầu và cuối), tọa độ x ở mỗi đường sẽ là (<span id="MathJax-Element-76-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="x1[y]">x1[y]x1[y] , <span id="MathJax-Element-77-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="x2[y]">x2[y]x2[y] và <span id="MathJax-Element-78-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="x3[y]">x3[y]x3[y] ) : <span id="MathJax-Element-79-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="x1[y]&lt;x2[y]&lt;x3[y]">x1[y]<x2[y]<x3[y]x1[y]<x2[y]<x3[y] . Ta xét hàng thứ y. Giả sử, ta xét <span id="MathJax-Element-80-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="x1[y−1]">x1[y1]x1[y−1] , <span id="MathJax-Element-81-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="x2[y−1]">x2[y1]x2[y−1] and <span id="MathJax-Element-82-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="x3[y−1]">x3[y1]x3[y−1] và số táo hiện giờ thu được là nhiều nhất. Từ đó ta có thể tối ưu cho hàng <span id="MathJax-Element-83-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="y">yy. Chúng ta cần tìm cách chuyển trạng thái. Gọi <span id="MathJax-Element-84-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Max[i][j][k]">Max[i][j][k]Max[i][j][k] là lượng táo nhiều nhất thu được đến hàng <span id="MathJax-Element-85-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="y−1">y1y−1 với 3 đường đang dừng ở cột <span id="MathJax-Element-86-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="i">ii, <span id="MathJax-Element-87-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="j">jj, và <span id="MathJax-Element-88-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="k">kk. Với hàng <span id="MathJax-Element-89-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="y">yy, thêm vào <span id="MathJax-Element-90-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Max[i][j][k]">Max[i][j][k]Max[i][j][k] số lượng táo ở các ô <span id="MathJax-Element-91-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="(y,i)">(y,i)(y,i) , <span id="MathJax-Element-92-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="(y,j)">(y,j)(y,j) and <span id="MathJax-Element-93-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="(y,k)">(y,k)(y,k). Vì chúng ta đang đi xuống. Sau đó, chúng ta xét đến những đường có thể sang phải. Để tránh việc giao nhau, ta xét lần lượt các bước ở trái, phải rồi giữa.

    Bài luyện tập thêm:

    Note: Khi gặp một bài toán, hãy để ý xem nó có được giải trong thời gian đa thức không. Nếu có, thử xác định trạng thái của nó, cách chuyển trạng thái, và nếu không chuyển được trạng thái, hãy thử tối ưu nó về một bài QHĐ (như ví dụ ở trên).

    Những bài đã đề cập ở trên: