Introduction to Dynamic Programming

To know the Dynamic Programming or better understanding Recursion 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
ii. Dynamic Programming II: Text Justification, Blackjack
iii. Dynamic Programming III: Parenthesization, Edit Distance, Knapsack

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

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 :

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
2. topo order =i=n, n-1,....0

total time = O(n^2)

1. 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];
    }
}