DAA: Dynamic Programming

Dynamic Programming

Introduction

The technique of breaking a problem statement into subproblems and using the optimal result of subproblems as an optimal result of the problem statement is known as dynamic programming. This technique uses an optimized approach and results in optimal solutions.

For example, let us see the Fibonacci sequence (A sequence in which the sum of two numbers is the third number in the sequence).

0 1 1 2 3 5 ……

This can be solved using the equation:

Fibonacci (n) = Fibonacci (n-1) + Fibonacci (n-2)

Thus the problem statement is broken down into subproblems (n-1) AND (n-2), which gives the optimal result, the next number in the sequence. Hence, it is a good example of dynamic programming.

The main contrast between divide and conquer and dynamic programming is in DP, there can be overlapping subproblems, but in the case of D and C, the subproblems are independent.

Dynamic programming cannot solve all the problems. There are several algorithms that can be solved using greedy and divide and conquer techniques. The difference between recursion and DP recursion is memoization in DP. If the subproblem does not require memorization, in any case, DP cannot solve that problem.

Major components in Dynamic programming: The Following are components of dynamic programming:

1. Recursion - To solve the problems recursively.
2. Memoization – To store the precomputation of subproblems to use further.

DP = RECURSION + MEMOIZATION

Properties of dynamic programming strategy

There are two strategies that show whether a given problem can be done with DP or not are:

1. Overlapping subproblems - A recursive solution that contains a small recursive solution for subproblems.
2. Optimal substructure - An optimized solution to a problem that has optimal subproblems.

Approaches of dynamic programming: Following are the basic approaches of DP -

1. Top-Down Approach: In this approach, the problem is broken into subproblems, and the result at each sub problem is remembered. When a result at subproblem is needed again further, it is first checked in the memory stage and then used.
2. Bottom-Up Approach: This approach follows the idea of computing first and moves backward. It is done to avoid the process of recursion. The smaller inputs at each step in the bottom-up approach contribute to form larger ones.

Examples of DP:

1. 0-1 Knapsack problem
2. Traveling salesman problem
3. Chain Matrix multiplication
4. String algorithms – Longest common subsequence, Longest increasing sequence etc.
5. Optimized graph algorithms and many more.