AlgoZenith
VG Frameworks
Dynamic
Programming
[Part-1]
Key Concepts
VG DP Frameworks
Steps
Time Complexity Analysis
Code Template
FAQs
SWIPE LEFT >>>
VISIT FOR MORE
www.maang.in/learn
Key Concepts
DP, a glorified recursion with caching,
means an optimized version of recursion. If
once the value is calculated then no need
to re-evaluate it.
Key Properties are:
a). Overlapping sub-problems should exist
b). Optimal Substructure : The idea is if a
function f(x) is dependent on some
functions f(y) and f(z), then x is optimally
dependent on y and z.
VISIT FOR MORE
SWIPE LEFT >>> www.maang.in/learn
VG DP Frameworks
Form 1: Take/not take, e.g. 0-1 Knapsack
Problem
Form 2: Starting at or Ending at, e.g.
Longest Common Substring (LCS)
Form 3: Multisequence DP, e.g. Longest
Common Subsequence
Form 4: LR DP, e.g. Rod Cutting Problem
Form 5: Game DP, e.g. Subtraction Game
VISIT FOR MORE
SWIPE LEFT >>> www.maang.in/learn
VG DP Frameworks
Complete Playlist Available at my
YouTube Channel!
VISIT FOR MORE
SWIPE LEFT >>> www.maang.in/learn
Steps
Identify the form of the problem
Decide States and Meaning
Transition Designing -> (design the
transitions between different states
based on the choices made. Each
transition represents how you move
from one state to another based on
some decision or action.)
Check Time Complexity
VISIT FOR MORE
SWIPE LEFT >>> www.maang.in/learn
Form 1: Take/Not Take
Consider an AlgoZenith workshop where
there are N problems. Each i-th problem
takes Ti time and provides S i skills. You have i
X units of time and K available slots. Find the
maximum skills you can gain.
Ti -> 3 5 4 2 1 X=6
S i -> 3 4 2 3 1 K=2
1. Identify
i the constraints:
∑ t <= x and count <= K
2. Identify the states:
DP[level, time_taken, item_taken]
VISIT FOR MORE
SWIPE LEFT >>> www.maang.in/learn
Design Transitions
3. Design Transitions :
Suppose you are at index (level) = 3. This
means all the previous levels have been
computed and stored. Now, at the current
level, you have two choices, either take/not
take To calculate the
max skill gained
we’ll select the
DP(level, time_taken, item_taken) max value we
get from these
Not Take Take two branches
DP(level+1, DP(level+1,
time_taken, time_taken + T[level]
item_taken) item_taken + 1)
VISIT FOR MORE
SWIPE LEFT >>> www.maang.in/learn
Time Complexity
4. Formula to evaluate Time Complexity:
(No. of states)*(1+Avg. transition cost per state)
DP(level, time_taken, Item_taken)
level = index -> [0,......,N]
time_taken -> [0,.......,X]
item_taken -> [0,.......,K]
No. Transition States = 2 (Take and not take)
T.C. -> O(N*X*K)*(1+2) = O(N*X*K)
VISIT FOR MORE
SWIPE LEFT >>> www.maang.in/learn
Form 1: Code Template
VISIT FOR MORE
SWIPE LEFT >>> www.maang.in/learn
Course Available for Free!
Master Dynamic Programming with our
comprehensive course! Sign up today at
https://www.maang.in & unlock everything
you need to know about one of the most
important topics in tech. Don't miss out!
VISIT FOR MORE
SWIPE LEFT >>> www.maang.in/learn
FAQ’s on Form 1
Identify if Subset Sum Exist
Print Solution of Subset sum if exist
0-1 Knapsack Problem
House Robber Problem
Coin Change Problem
Longest Increasing Subsequence
Jump Game II (LeetCode 45)
Best Time to Buy & Sell Stock II(LeetCode 122)
Decode Ways (LeetCode 91)
VISIT FOR MORE
www.maang.in/learn
