Dynamic Programming

In mathematics and computer science, dynamic programming (DP) is a method of solving problems exhibiting the properties of overlapping subproblems and optimal substructure that takes much less time than naive methods. (from wiki)

DP is a powerful technique. It is a 3 step approach. We break the problem into smaller sub-problems (states), solve them and using the solutions to sub-problems, solve the original problem. The sub-problems are also divided into further sub-problems recursively till we get a base case.

The classic coin denomination problem is a good example. If given a set of coins V {V1, V2, ... Vn}, you have to find the least number of coins required for a number S. Let's say you have coins with denominations V = {1, 3, 5} and you need to find the least coins for sum S = 11. If you know the least coins for sums S-Vj i.e. 10 (11-1), 8 (11-3), 6 (11-5) then you can find for S = 11. The sums S-Vj are sub-problems for this problem.

Coinsi = 0 for i = 0
            = min Coinsi-Vj  for all Vj in V for i > 0

coinDenominations(coins V, sum S):
    coins[1 to s] = infinity
    deno[1 to S] = undefined
    coins[0] = 0
    for i = 1 to n: 
        for coin Vj in set of coins V and Vj <= i:
            if ( coins[i-Vj] + 1 < coins[i] ): 
                coins[i] = coins[i-Vj] + 1
                deno[i] = Vj

(n, coins):
    mincoins = new int?[n +1]
    deno = new int[n +1]
    mincoins.fill(null) // or int.max
    mincoins[0] = 0
    for i = 1, i <= n, i++:
        for coin in coins:
            if i-coin < 0:
                continue
            if mincoins[i] == null ||
                mincoins[i-coin] +1 < mincoins[i]:
                mincoins[i] = mincoins[i-coin] +1
                deno[i] = coin
    // min # coins
    return mincoins[n]
    // coins for min coins
    mcoins = new
    i = n
    while i > 0:
        mcoins.add(deno[i])
        i -= deno[i]
    return (mincoins[n], mcoins)

The least coins for S are obtained from coins[] and the coins are obtained from deno[]. For S = 11, coins are 3 (1, 5, 5). Time efficiency is O(S*n) where S is the required sum and n is the number of coins. The greedy approach for this problem would not work in some cases. For example, with coins V = {1, 7, 10} and for S = 14, the greedy approach would consider coin with maximum denomination 10 and would end up with (10, 1, 1, 1, 1). But for 14, it should be (7, 7).

Below is another problem where we want to find the longest increasing subsequence from given numbers. In below case, the numbers in bold is the longest one i.e 3, 4, 6, 7 and not 3, 4, 8.

1  2  3  4  5  6   i
5, 3, 4, 8, 6, 7   A[]

The approach in this problem is to maintain seqCount[] for every n. Initially it is 1 i.e. itself. previous[] holds the previous number in the sequence from any number. For any number i in the list, we compare the seqCount for all the predecessors j of i,  i.e. j = i-1 to 1. If we find a better seqCount, then we update it and also previous[]. For example, at i=4, A= 8 and seqCount = 3. At i=5, A = 6, seqCount = 1 initially as 6 < 8. Then we compare 6 to 4 (whose sqlCount is 2) and so we get seqCount as 3.

seqCounti = 1 initially for all i
     = max(1 + seqCountj) for j < i and Ai > Aj

longestIncreasingSubsequence(int[] A):
    seqCount = new [a.length]
    seqCount[..] = 1
    previous = new [a.length]
    previous[..] = -1
    for i = 0, i < a.length, i++:
        for j = i-1, j >= 0, j++:
            if a[j] <= a[i]:
                if seqCount[j] +1 > seqCount[i]:
                    seqCount[i] = seqCount[j] +1
                    previous[i] = j

[] (a):
    count = new [n]
    previ = new [n]
    maxcount = 1
    lasti = 0
    for i = 1, i < a.length(), i++:
        for j = 0, j <= i-1, j++:
            if a[j] > a[i]:
                continue
            if count[j] +1 > count[i]:
                count[i] = count[j] +1
                previ[i] = j
                if count[i] > maxcount:
                    maxcount = count[i]
                    lasti = i
    stack sequence = new
    i = lasti
    while i >= 0:
        sequence.push(a[i])
        i = previ[i]
    return sequence

Time efficiency is O(n^2). We can make the time efficiency better - instead of looking for predecessors of i sequentially (for j = i-1 to 1), when we find the largest number lesser than i, we break out of the inner for loop. This can done using a binary tree and the lookup to find the largest number lesser than i would take O(logn) time. So efficiency would be O(nlogn).

DP has polynomial complexity but the issue is usually space and not time. I might update this article as I encounter interesting complex problems that I am able to solve. :P

[Hat tip to D at topcoder]