15,996,429 members
Articles / General Programming / Optimization

Dynamic Programming – What, How & When

Rate me:
10 Oct 2020CPOL5 min read 23.7K   1   22
An optimization programming technique
In this post, we will take a look at dynamic programming which is an optimization programming technique.

There are many programming techniques, which when applied appropriately to a specific situation, leads to efficient results (either time wise or space wise or both). `Dynamic Programming` (`DP`) is one such optimization concept.

Quote:

Not to be confused with Dynamic programming language or Dynamic type in C#

What Is?

Dynamic programming is solving a complicated problem by breaking it down into simpler sub-problems and make use of past solved sub-problems.

Quote:

Dynamic Programming is mainly an optimization over plain recursion.

Intent of this post is to easily understand and visualize the concept of DP. Thus, let’s use Fibonacci series as an example to understand this in detail.

Quote:

Fibonacci Series is a sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.

0, 1, 1, 2, 3, 5, 8, 13, 21…

When To?

It is best applied to problems that exhibits Overlapping Subproblems & Optimal Substructure.

Following is how our Fibonacci problem fib(4) breakdown would look like:

Problem tree for fib(4)

We can see that `fib(0)`, `fib(1)` & `fib(2)` are occurring multiple times in the graph. These are `overlapping subproblems`.

Quote:

Binary search tree would not fall into same category. There would no common subproblem by binary search definition itself.

We can see for optimal solution of `fib(4)`, we would need optimal solution of `fib(3)` & `fib(2)` and so on. This tells it has `optimal substructure`.

Quote:

Longest path problem does not exhibit as such. Optimal solution for longest distance between A & C might not be optimal for B & C that involves A.

How To?

It’s not an unknown or a new technique. Our brain does it almost all the time. Let’s use Fibonacci series as an example to understand this and then we will apply DP to solve it programmatically.

Logically …

Let’s say, I ask, what is the 4th number in the Fibonacci series? You would work from 0, 1, 1, etc. and come to `fib(4) = 2`. Now, if I ask, what is the 5th number? Would you restart from 0, 1, 1..? Or you would just make use of `fib(4)` you just solved and get `fib(5)`?

You see – it’s obvious, you will make use of previous solved result and right away come up with `fib(5)` instead of starting from 0. In programming language, this is `tabulation` using calculated `fib(4)` & `fib(3)`.

Quote:

`Tabulation` is a technique of starting from smallest sub-problem and storing the results of entries until target value is reached.

Let’s say, now I ask to calculate `fib(8)`. Our natural way of working on it would be to first find `fib(7)` & `fib(6)`. In order to know `fib(7)`, we will figure out `fib(6)` & `fib(5)` and hence forth. With `fib(7)`, we already traversed through `fib(6)`. This is another approach where we calculated the next subproblem and keep on storing them in case of need later. In programming language, this is `memoization`.

Quote:

`Memoization` is a technique of storing the results of expensive function calls and returning the cached result when the same inputs occur again.

DP breaks the problem into sub-problems and uses `memoization` or `tabulation` to optimize. We will understand about them with examples below.

Programmatically in Action …

In order to compare the optimization cost, we will use recursion as another way to solve the problem.

C#
```static void Main(string[] args)
{
Stopwatch stopwatch = new Stopwatch();

Console.WriteLine(\$"Fibonacci Recursive:");
for (int i = 30; i <= 50; i+=5)
{
stopwatch.Reset();
stopwatch.Start();
var _ = FibonacciRecursive(i);
stopwatch.Stop();
Console.WriteLine(\$"{i}th took time: ({stopwatch.Elapsed})");
}

Console.WriteLine(\$"Dynamic Programming:");
for (int i = 30; i <= 50; i+=5)
{
stopwatch.Reset();
stopwatch.Start();
var _ = FibonacciDPTabulation(i);
stopwatch.Stop();
Console.WriteLine(\$"{i}th took time: ({stopwatch.Elapsed})");
}
}

static long FibonacciRecursive(int number)
{
if (number <= 1)
return number;
return FibonacciRecursive(number-2) + FibonacciRecursive(number - 1);
}

static long FibonacciDPTabulation(int number)
{
long[] arr = new long[100];
arr[0] = 1; arr[1] = 1;
for( int x=2; x <= number; x++)
{
arr[x] = arr[x-1] + arr[x-2];
}
return arr[number];
}```

With the above code, we got the following output:

 Recursive Dynamic Programming (Tabulation) Dynamic Programming (Memoization) 30th took time (00:00:00.0090536) (00:00:00.0002756) (00:00:00.0183122) 35th took time (00:00:00.0908688) (00:00:00.0000037) (00:00:00.0000009) 40th took time (00:00:00.9856354) (00:00:00.0000006) (00:00:00.0000011) 45th took time (00:00:10.7981258) (00:00:00.0000006) (00:00:00.0000008) 50th took time (00:02:24.8694889) (00:00:00.0000006) (00:00:00.0000008)

Difference is astonishing! DP is too fast in comparison. Just look at the 50th time difference.

Quote:

With simple iterative approch, Fibonacci Series can be calculated in the same ballpark time as of DP. Current example is just to keep things simple and understand the DP concept. Please look at the end of post for common examples that would clarify where DP would be of real help over recurrsion. (& iterative approach would be difficult to code)

The above approach of DP is considered `Bottom-Up approach` as we started with bottom (lowest term) and then moved to the highest one. This is `tabulation`. We keep on filling on the cache here till we reach the target.

Alternatively, there is a `Top-down approach`. We start solving from highest term and store solutions of sub problems along the way. This is `memoization`. A code for this approach would look like:

C#
```private static Dictionary<int, long> memo
= new Dictionary<int, long>();

static long FibonacciDPMemoization(int number)
{
if (number == 0 || number == 1) {
return number;
}

// see if we've already calculated this
if (memo.ContainsKey(number)) {
return memo.GetValueOrDefault(number);
}

long result = FibonacciDPMemoization(number - 1)
+ FibonacciDPMemoization(number - 2);

return result;
}```

`memoization` is sometimes simpler to understand and write code because of it’s a natural way of solving.

Quote:

Generally, `tabulation` outperforms `memoization` by a constant factor. This is because of no overhead for recursion and can be stored as a pre-allocated array. We first calculate and store the value of a sub problem repeated most number of times here.

Few Common Examples?

• Tower of Hanoi
• Checkerboard
• Egg dropping puzzle
• Matrix chain multiplication

Details of these above problem can be read here.

Beware?

Apart from avoiding problems that do not have Overlapping Subproblems & Optimal Substructure, one needs to understand we are doing a trade here – space for time!

We can always discuss that though DP is using extra space to store the sub-problems data, but in turn helps save in memory calculation which could be expensive. Thus, in case of constrained space, we need to evaluate usage of DP.

Keep learning!.

Written By
Architect Intuit India
India

A software professional for more than 17+ years building solutions for Web and Desktop applications.

Currently working at Intuit India.

Website: Learn By Insight
Github: Sandeep Mewara

Strongly believe in learning and sharing knowledge.

 First Prev Next
 tail recursion in C# ... and, other Fibonacci algorithms BillWoodruff12-Oct-20 22:15 BillWoodruff 12-Oct-20 22:15
 Re: tail recursion in C# ... and, other Fibonacci algorithms Sandeep Mewara13-Oct-20 1:51 Sandeep Mewara 13-Oct-20 1:51
 Re: tail recursion in C# ... and, other Fibonacci algorithms BillWoodruff13-Oct-20 6:44 BillWoodruff 13-Oct-20 6:44
 Re: tail recursion in C# ... and, other Fibonacci algorithms Sandeep Mewara14-Oct-20 6:44 Sandeep Mewara 14-Oct-20 6:44
 Re: tail recursion in C# ... and, other Fibonacci algorithms BillWoodruff14-Oct-20 7:27 BillWoodruff 14-Oct-20 7:27
 A faster tabulation ? Patrice T12-Oct-20 11:36 Patrice T 12-Oct-20 11:36
 Re: A faster tabulation ? BillWoodruff12-Oct-20 22:02 BillWoodruff 12-Oct-20 22:02
 Re: A faster tabulation ? Patrice T13-Oct-20 0:32 Patrice T 13-Oct-20 0:32
 Re: A faster tabulation ? Sandeep Mewara13-Oct-20 1:41 Sandeep Mewara 13-Oct-20 1:41
 Re: A faster tabulation ? Sandeep Mewara13-Oct-20 2:09 Sandeep Mewara 13-Oct-20 2:09
 connotations of "dynamic programming" ? BillWoodruff12-Oct-20 2:43 BillWoodruff 12-Oct-20 2:43
 Re: connotations of "dynamic programming" ? Sandeep Mewara13-Oct-20 1:37 Sandeep Mewara 13-Oct-20 1:37
 Benchmark the 3 methods Patrice T11-Oct-20 18:26 Patrice T 11-Oct-20 18:26
 Re: Benchmark the 3 methods Sandeep Mewara11-Oct-20 20:39 Sandeep Mewara 11-Oct-20 20:39
 Re: Benchmark the 3 methods Sandeep Mewara11-Oct-20 21:07 Sandeep Mewara 11-Oct-20 21:07
 Re: Benchmark the 3 methods Patrice T12-Oct-20 0:47 Patrice T 12-Oct-20 0:47
 Re: Benchmark the 3 methods Sandeep Mewara13-Oct-20 1:32 Sandeep Mewara 13-Oct-20 1:32
 Poor Comparison SledgeHammer0110-Oct-20 5:23 SledgeHammer01 10-Oct-20 5:23
 Re: Poor Comparison Sandeep Mewara10-Oct-20 9:37 Sandeep Mewara 10-Oct-20 9:37
 Re: Poor Comparison SledgeHammer0111-Oct-20 5:11 SledgeHammer01 11-Oct-20 5:11
 Re: Poor Comparison Sandeep Mewara11-Oct-20 5:17 Sandeep Mewara 11-Oct-20 5:17
 Re: Poor Comparison Sandeep Mewara13-Oct-20 2:10 Sandeep Mewara 13-Oct-20 2:10
 Last Visit: 31-Dec-99 18:00     Last Update: 12-Sep-24 22:52 Refresh 1