Introducing to Dynamic Programming

At the earliest programming level, most people start to solve a problem using brute force algorithm because it’s easy to understand and implemented to any problems. When we move to higher level, the problem become complex and required more memory and time. At this level, we must do optimization. If you have built brute force or greedy algorithm, you may to do optimization by rebuilt your algorithm based on Dynamic Programming method.


Dynamic Programming is a method to solve any problems which have characteristic of overlapping subproblems and optimal substructure. This method invented by Richard Bellman at 1940.  The word programming is not related with computer programming, but referred form mathematical term mathematical programming. Thus, the word program in this context mean optimal plan. Different from another method like brute force or greedy, Dynamic Programming not only goal oriented algorithm, but has capability to increase memory efficency and speed optimization.

To make this more understanding, we will solve problems that have following characteristic:

1. Overlapping Subproblems
2. Optimal Substructure

Overlapping Subproblems

Before we try to solve this problem using Dynamic Programming, please read my article about What is Overlapping Subproblems. Use the example from that article, we will solve fibonacci sequence using Dynamic Programming method.

From the described call tree above, there is a subproblem repetition each time we want to know the value of n>=2. Thus, higher n value need more execution time and memory usage. In Big-O notation, the Fibo function take O(c^n) time or increase exponentially. There are two paradigm to increase effeciency; Top-Down and Bottom-Up. Both paradigm only need O(n) time to find n-th value of fibonacci series.

In Top-Down paradigm, first we need to break down a problem into smaller subproblems. Then calculate and save the result. The technique to save the result called as memoization.

To solve the fibonacci series using Top-Down paradigm, first we need to initilize which known solution and unknown solution. Then, create the array container containt known solution and to save every result of Fibo function result. The algorithm should be

1 2 3 4 5 6 7

var m = {0, 1, 1} Function FiboTopDown(n) if key n not exist in array m then m[n] = FiboTopDown(n-1) + FiboTopDown(n-2) else return m[n] end

Because in this paradigm we need to store every value into array, the memory usage need O(n) allocation.

The Bottom-Up paradigm is opposite of Top-Bottom paradigm where we calculate the smallest n value first. Then use that values to calculate bigger n value. The algorithm should be

1 2 3 4 5 6 7 8 9 10 11 12

Function FiboBottomUp(n) var prevVal = 1, curVal = 1 if n<2 then return 1 else repeat until n-1 time var newVal = prevVal + curVal prevVal = curVal curVal = newVal end return curVal end

Because in this paradigm only need loop until n-1 time, the memory usage need O(1) allocation.

Optimal Substructure

Before we try to solve this problem using Dynamic Programming, please read my article about What is Optimal Substructure. Use the example from that article, we will find shortest path using Dynamic Programming method.

Our goal is to find shortest path from S to G, but the we must to transit at one point first before reach G point. There is four transit point (A, B, C, D) beetwen S and G. Then, we can break down the main problem into two subproblems; the subproblem to find shortest distance from S to transit and subproblem to find shortest distance from transit to G. After that, calculate every sub-path in every subproblems. Form the calculation, we can find the shortest sub-path. Then, construct every shortest sub-path into compleate shortest path.

Let’s illustrate this problem using array. First subproblem should be {30, 25, 20, 15} and second subproblem should be {40, 60, 70, 100}. Solve this problem using naïve algorithm or brute force should be

1 2 3 4 5 6 7 8 9 10 11 12 13 14

shortest = {subProblemOne[1], subProblemTwo[1]} length = length of subProblemOne Function shortestNaive(shortest, i, j) if i <= length of subProblemOne then if shortest[1] + shortest[2] > subProblemOne[i] + subProblemTwo[j] shortest = {subProblemOne[i], subProblemTwo[j]} j = j + 1 if j >= 4 then i = i + 1 j = 1 shortestNaive(shortest, i, j) else return shortest end

The naïve algorithm above would need cost O(n^2) in execution time because this solution need to check every value for every array. Like Overlapping Subproblems before, we can optimize naive solution by implemented Top-Down paradigm and Bottom-Up paradigm.

Solve using Top-Down paradigm means we solve the problem from top level to bottom. But different form fibonacci sequence, in this case we don’t need memoization because we only need comparison beetwen before and current value. The algorithm should be

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

i = length of subProblemOne Function shortestTopDown(i) if i = 1 then return shortestOne, shortestTwo else if subProblemOne[i] < subProblemOne[i-1] shortestOne = subProblemOne[i] else shortestOne = subProblemOne[i-1] if subProblemTwo[i] < subProblemTwo[i-1] shortestTwo = subProblemTwo[i] else shortestTwo = subProblemTwo[i-1] i = i - 1

Solve shorthest path problem using Bottom-Up paradigm mean the problem solving is reversed from bottom to top level. The logic is quiete simpler than recurtion, because we only need loop to solve the problem. The algorithm should be

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Function shortestBottomUp(subProblem1, subProblem2) // Assume that subProblem1 and subProblem2 have same length var j = length of subProblem1 var shortest1 = subProblem1[1] var shortest2 = subProblem2[1] var i = 2 for i to j if subProblem1[i] < shortest1 then shortest1 = subProblem1[i] end if subProblem2[i] < shortest2 then shortest2 = subProblem2[i] end end return [shortest1, shortest2]

If you want the deeper understanding, you may read the study case of following problem in three different method (Brute Force, Greedy, and Dynamic Programming):

1. Solve The Knapsack Problem
2.  Solve Balanced 0-1 Matrix
3. Solve Matrix Chain-Products
4. Solve Sequence Aligments