DP vs Greedy what is dp (dynamic prgmming)

q. how dynamic prog works:
step 1 : breaks down the complex problm into simpler sub problem step 2 : finds optimum soln to these sub problms step 3 : store the results of sub problems ; this step is also known as memoization step 4 : reuse them so that same sub problem is calculcated more than once

q. (very imp) applicable to problems which are having properties of

1. overlapping sub problems : ek problem mei aise subproblems hai jo ek se jyaada time appear ho rhe hai so agar if we store the computed subproblems so we dont have to recompute same subproblems again and again
2. optimal sub structure

optimal sub structure : problem should be divisible

20250903_141758.heic

20250903_141758.heic

dynamic prog mei jab bhi recurssive approach aaye toh follow top down else jab itterative approach aaye toh follow bottom up

MULTISTAGE GRAPH:

1. it is directed weighted graph
2. it is multiple stages graph
3. nodes at any particular stage aren’t connected in same stage (2 is not connected with 3 and 3 is not connected with 2 same for others ) they can be connected to next stage (2 is connected with 6 which is present in stage 3, same for others) the problem we are gonna solve is we have to find minimum path from s to d

there are two approach in multistage graph BACKWARD FORWARD

STAGE 1: start vertex=1→S d[1]/d[S]=0

STAGE 2: d(1,2)=1 d(1,3)=22 d(1,4)=77

Stage 3 :