Dynamic programming

[Kevin Hoang]

Dr thấy cái tài liệu này cũng hay hay, và rất có ích. Mời các bạn tham khảo. Sẽ có phiên bản tiếng Việt, nhưng các bạn đọc trước phiên bản tiếng Anh này đã nhé!



Dynamic programming is a common and useful technique in writing programs. In this context, "programming" does not refer to coding, it refers to planning in a tabular format. The very hallmark of dynamic programming is that it stores intermediate results during the computation in one or more separate arrays. However, in doing so, sometimes it can result in a faster algorithm. Usually, dynamic programming is used to solve optimization problems, such as to determine the shortest, fastest, most profitable, least cost, etc. way of doing a task.
We shall consider the following problem. Suppose you are in a city with m horizontal roads and n vertical roads. The horizontal roads are numbered from 1 to m and the vertical roads are numbered from 1 to n as shown in the diagram below.

All the horizontal roads intersect with the vertical roads at the junctions. Each junction is labelled (i, j), where i is the number of the horizontal road and j is the number of the vertical road.
You are driving a car and is at the junction (1, 1), and your car is low in petrol, so you need to drive your car to the petrol station located at (m, n). As you have to meet an important client after filling up the petrol, so you need to reach the petrol station in the shortest possible time. However, the amount of petrol in your car is low, so you have to drive to the petrol using the shortest distance route. That is, you want to drive only rightward or downward, you do not want to waste petrol by driving leftward or upward. Also, the amount of time need to travel from a junction to any of its adjacent junctions is known, the amount of time varies from place to place because the amount of congestion at different places is not the same. You can assume that no time is needed to clear a junction.
What is the fastest route you should take to drive to the petrol station, and how much time is required?
We shall formalize the problem as follows. Let h(i, j) be the amount of time needed to drive from (i, j) to (i, j + 1), and v(i, j) be the amount of time needed to drive from (i, j) to (i + 1, j). Both h(i, j) and v(i, j) are known for all junctions (i, j). We shall answer the second question on the time required first.
Using the dynamic programming approach, we will need to define another array t of size m by n, where t(i, j) is the minimum amount of time needed to drive from (i, j) to (m, n).
Let us define the basis first:

• t(m, n) = 0.
• t(m, j) = t(m, j + 1) + h(m, j), for j = 1 to n - 1.
• t(i, n) = t(i + 1, n) + v(i, n), for i = 1 to m - 1.

The first is simple: if you are already at (m, n), you don't need to spend any more time travelling. The second base case arise because if you are already at horizontal road m, then you can only move right. Similarly, if you are already at vertical road n, then you can only drive downwards, so this is how the third base case is derived. With the above three conditions, we can fill up the last row and column of the array t backwards from t(m, n).
Next, we define the recurrence:

• t(i, j) = min{t(i, j + 1) + h(i, j), t(i + 1, j) + v(i, j)}.

This recurrence relation should be self-explanatory: suppose we already computed t(i, j + 1) and t(i + 1, j), then we can find the fastest way to reach (m, n) from (i, j) using the recurrence relation. The recurrence is the one which allows us to fill up the remaining entries of the table t.
Thus, we can derive an algorithm to compute the entries of the table t:

// Basis
t(m, n) = 0
for j = n - 1 downto 1
    t(m, j) = t(m, j + 1) + h(m, j)
for i = m - 1 downto 1
    t(i, n) = t(i + 1, n) + v(i, n)

// Recurrence
for i = m - 1 downto 1
    for j = n - 1 downto 1
        if t(i, j + 1) + h(i, j) < t(i + 1, j) + v(i, j)
            t(i, j) = t(i, j + 1) + h(i, j)
        else
            t(i, j) = t(i + 1, j) + v(i, j)

Notice that the correctness of this algorithm is from the fact that the array t is built backwards from bottom up as well as right to left. The algorithm terminates when we have computed t(1, 1), which is the minimum time required to drive from (1, 1) to (m, n).
So we have solved half the problem. How do we find out the route which takes the shortest time?
To do this, we will augment the above algorithm with another array r of size m by n, where r(i, j) is either the value RIGHT or DOWN, indicating driving rightward or downward will lead to the fastest route from (i, j) to (m, n). Again we define the basis and recurrence for r:

• r(m, j) = RIGHT, for j = 1 to n - 1.
• r(i, n) = DOWN, for i = 1 to m - 1.
• r(i, j) = RIGHT, if t(i, j + 1) + h(i, j) < t(i + 1, j) + v(i, j), for j = 1 to n - 1 and i = 1 to m - 1.
• r(i, j) = DOWN, if t(i, j + 1) + h(i, j) >= t(i + 1, j) + v(i, j), for j = 1 to n - 1 and i = 1 to m - 1.

Note that r(m, n) is undefined, but that is not important. We will use the array r to determine the route from (1, 1) to (m, n).
We modify the algorithm thus:

// Basis
t(m, n) = 0
for j = n - 1 downto 1
    t(m, j) = t(m, j + 1) + h(m, j)
    r(m, j) = RIGHT
for i = m - 1 downto 1
    t(i, n) = t(i + 1, n) + v(i, n)
    r(i, n) = DOWN

// Recurrence
for i = m - 1 downto 1
    for j = n - 1 downto 1
        if t(i, j + 1) + h(i, j) < t(i + 1, j) + v(i, j)
            t(i, j) = t(i, j + 1) + h(i, j)
            r(i, j) = RIGHT
        else
            t(i, j) = t(i + 1, j) + v(i, j)
            r(i, j) = DOWN

Finally, we can determine the shortest time route by backtracking using the array r:

// Backtracking
i = 1
j = 1
while i < m and j < n
    if r(i, j) == RIGHT
        print "Drive rightward from (i, j) to (i, j + 1)"
        j = j + 1
    else  // r(i, j) == DOWN
        print "Drive downward from (i, j) to (i + 1, j)"
        i = i + 1

Although the algorithm seems a little bit complicated, it actually achieves the best possible time complexity. Since both t and r are of size m by n, filling up both tables in the basis and recurrence steps take O(mn) time. For the backtracking step, we will move rightwards a total of n - 1 times and downwards a total of m - 1 times, so the time complexity is O(m + n). Hence, the total time complexity is still O(mn). Intuitively, this is the best possible time complexity since there are mn junctions in the problem, so the time complexity is actually linear with respect to the size of the problem.
We shall conclude this miniature with another exercise in dynamic programming known as the subset sum problem.
Formally, we define the subset sum problem as follows. You are given:

• A set of n positive integers, S.
• A positive number, m.

Is there a subset of S whose elements sum up to m? For example, if S = {2, 3, 5, 7, 11} and m = 14, then the answer is yes because 2 + 5 + 7 = 14; and if S = {2, 3, 5, 7, 11} and m = 6, then the answer is no.
Give an algorithm that uses dynamic programming to solve the subset sum problem, and analyze the time complexity of your algorithm in terms of n and m.

Chúc mọi thành viên cộng đồng C Việt thành công và học tập tốt!

[rox_rook]

Dynamic programming : divide and conquer with a table.
Application to :
- Computing combinations
- Knapsack problem

Counting Combinations

To choose r things out of n, either :
- Choose the first item. Then we must choose the remaining r-1 items from the other n-1 items. Or
- Don't choose the first item. Then we must choose the r items from the other n-1 items.

There fore :
[C(r,n) = C(n-1, r-1) + C(n-1, r) /*C tổ hợp chập r của n phần tử*/

Divide and Conquer
This gives a simple divide and conquer algorithm for finding the number of combinations for n things chosen r at a time.

function choose ( n, r )
if r = 0 or n = r then return (1) else
return ( choose ( n-1, r-1) + choose ( n-1, r ) )

Correctness proof : A simple induction on n.
Analysics : Let T(n) be the worst case running time of choose (n, r ) over all possible values of r.

Then
T(n) :
+ c if n = 1
+ 2T(n-1) + d otherwise.
for some constant c, d.
Hence :
T(n) = 2T(n-1) + d
= 2(2T(n-2) + d ) + d
= 4T(n-2) + 2d + d
= 4(2T(n-3) + d ) + 2 + d
= 8T(n-3) + 4d + 2d + d
= 2^i T(n-i) + d.Sum (j=0;i-1)2^j
= 2^(n-1) T(1) + d.Sum(j=0;n-2) 2^j
= (c + d)2^(n-1) - d.
Hence T(n) = O(2^n) --> sucks^^

Example

The problems is, the algorithm solves the same problems over and over again :


Repeated Computation


Pascal's triangle. Use a table T[0..n, 0...r]

T[i,j] holds C(i,j)

function choose (n,r)
for i:= 0 to n - r do T[i,0] = 1;
for i:= 0 to r do T[i,j] = 1;
for j:= 1 to r do 
     for i:= j+1 to n - r + j do 
           T[i,j] = T[i-1,j-1] + T[i-1,j]
return ( T[n,r] )

Initialization


General Rule
To fill in T[i,j] we need T[i-1,j-1] and T[i-1, j] to be already filled ịn


Fill in the Table
Fill in the columns from left to right. Fill each of the columns from top to bottom.



Analysis
How many table entries are filled in ?
(n - r + 1 )(r+1) = n.r + n - r^2 + 1 <= n(r+1) + 1
Each entries takes time O(1), so the total times required is O(n^2), and this much better than O(2^n).

Dynamic Programming
When divide and conquer generates a large number of identical subproblems, recursion is too expensive
Instead, store solutions to subproblems in a table. This technique called dynamic programming.

Dynamic Programming Techniques

Identification :
- Devise divide-and-conquer algorithm.
- Analyze-running time is exponential.
- Same subproblems solved many times.

Construction :
- Take part of divide-and-conquer algorithm that does the "conquer" part and replace recursive calls with table lookups.
- Instead of returning a value, record it in a table.
- Use base of divide-and-conquer to fill in start of table.
- Devise "look-up template"
- Devise for-loops that fill the table using "look-up Template"


(to be continued )