Introduction to Dynamic Programming
Published: 2022-06-09 09:08:24

To know the Dynamic Programming or better understanding [Recursion](https://dev.to/insanity_xi/recursion-101-2gcd) as pre-requisite is the must.

> What is Dynamic Programming?
> What are the uses of Dynamic Programming?
> Dynamic Programming, and its necessity.
> How Dynamic Programming makes our life easier?

Introductory video links by Mit
:
[i. Dynamic Programming I: Fibonacci, Shortest Paths](https://www.youtube.com/watch?v=OQ5jsbhAv_M&list=PLcDimPvbmf
T8qAxD6JH_kmXiQwTNcoK78)
[ii. Dynamic Programming II: Text Justification, Blackjack](https://www.youtube.com/watch?v=ENyox7kNKeY&list=PLcDimPvbmf
T8qAxD6JH_kmXiQwTNcoK78&index=2)
[iii. Dynamic Programming III: Parenthesization, Edit Distance, Knapsack](https://www.youtube.com/watch?v=ocZMDMZwhCY&list=PLcDimPvb
mfT8qAxD6JH_kmXiQwTNcoK78&index=3)

Concept introduced by Richard Bellman, a Technique that helps programmers to get optimal solution of the problems having overlapping/repeating sub problems.

It is upgraded or effective way to solve recursive problem, only condition is that they should have overlapping sub problems. Hence, Recursion is prerequisite. Learn More about [recursion](url)

if problems don't overlap, algorithm like Merge Sort cannot be solved with DP, as their subproblems do not overlap.

**Techniques of Dynamic Programming**

I. Memoized DP Algorithms:
We put solution of solved subproblem in a Data Structre, if we have solved the problem, no need to solve again. we will use the existing solution.


in case of Fibonacci series :
memo=[]
fib(n):
if n in memo : return memo[n]
if n<2 : f=1
else: f= fib(n-1) + fib(n-2)
memo[n]=f
return f

 


- Memoized calls only costs O(1), constant time.

- fib(K) only recurses the first time and called as Fibonacci of k

- number(#) of non- memoized cost is n
   fib(1), fib(2)........fib(n)
- The non recursive work per call is constant, O(1), then total time O(n).
- time= number of subproblems . (time for each subproblem)= n. O(1)
-- do not count memoised recursion

Bottom Up DP algorithm :

fib={}
for k in rage (k):
if k<2: f=1
else: f= fib(k-1)+ fib(k-2)
 fib[k]=f
return fib[n]

exactly same computation as the memoise version
- topological sort of subproblem dependency DAG

**Shortest Paths**

shortest path from s-v for all V :
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/c6ytquvqzov17lstxtkp.png)
v^2 is number of subproblem in this case 
it is Bellman ford algorithm in disguise, gussing the last edge is helpful
**5 easy steps to DP**

1. Define Subproblems, and number of subproblems  
2. guess(part of the solution)
3. relate subproblems to the solution 
4. Recurse and Memoize 
or  Build DP table bottom up
5. Solve original Problem

Things to keep in mind while solving a DP problem:
- number of subproblems 
- number for the guess 
- time/subproblem 
- the number of subproblem recurrence is acyclic i.e. has topological order
- total time 

 **text justification** 
split text into "good" lines
text= list of words
badness(i,j)- use  words i(first word of first line) to j(first word to second line) as a one line.

badness= infinity- bad lines, if they do not fit.
otherwise
(page width- total width )^3 (a simple quantity, measure  ) 
1. subproblems: the remaining words after first line, we call it  suffixes words and denoted as [i:].
number of subproblems: n
2.guess: where to start the 2nd line
number of guess or choices: <=n-i=O(n)
3.recurrence: DP(i)= min( DP(j)+badness(i,j) )
for j in the range(i+1, n+1) 
 time/subproblem= O(n)
Base case= DP(n)=0, n is last word so no word after n
4. topo order  =i=n, n-1,....0

total time = O(n^2)

5. original problem = DP(0)

 Parent pointers: remember which guess was best
parent[i]=argmin(....)= j value
0->parent[0]->parent[parent[0]]



**Problem 1: Fibonacci Series**

```
class Solution {
    public int fib(int n) {
        if(n==0 || n==1) return n;
        int[] dp = new int[n+1];
        dp[0]=0;
        dp[1] =1;
        for(int i=2;i<=n;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        
        return dp[n];
    }
}

```

**Problem 2: n-th tribonacci Series**

```
class Solution {
    public int tribonacci(int n) {
        if(n==0 ){
            return 0;
        }
        else if(n==1 || n==2){
            return 1;
        }
        int dp[]= new int[n+1];
        dp[0]=0;
        dp[1]=1;
        dp[2]=1;
        for(int i =3;i<=n;i++){
        dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
        }
        return dp[n];
    }
}

```