Skip to content

rajshekharbind/Dynamic-Programming

Folders and files

NameName
Last commit message
Last commit date

Latest commit

Β 

History

2 Commits
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 

Repository files navigation

πŸš€ Dynamic Programming Roadmap with Smart Algorithm Steps

A topic-wise DP roadmap written in a sorted algorithm format so every problem becomes easy to understand and revise.


🧠 UNIVERSAL DP ALGORITHM (Use for Every Problem)

βœ… Smart DP Steps

1) Identify STATE β†’ what variables change?
2) Identify CHOICES β†’ what options do I have?
3) Write RECURSION
4) Add BASE CASE
5) Store answer in DP array (Memoization)
6) Convert into loops (Tabulation)
7) Optimize space if possible

🎯 Golden DP Formula

state = minimum changing parameters
answer = best among all choices

🟒 EASY DP TOPICS (Foundation)

Goal: Build DP thinking from recursion


1) Fibonacci ⭐

🧩 Algorithm Thinking

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

βœ… Smart Steps

  • state β†’ n
  • choice β†’ solve n-1 and n-2
  • base β†’ n <= 1
  • store dp[n]
  • convert to loop

2) Climbing Stairs ⭐⭐

🧩 Algorithm

dp[i] = dp[i-1] + dp[i-2]

βœ… Smart Steps

  • state = stair index
  • choices = 1 step / 2 step
  • answer = sum of both ways
  • same as Fibonacci pattern

3) Frog Jump ⭐⭐

🧩 Algorithm

dp[i] = min(
   dp[i-1] + abs(h[i]-h[i-1]),
   dp[i-2] + abs(h[i]-h[i-2])
)

βœ… Smart Steps

  • state = current stone
  • choices = jump 1 or 2
  • answer = minimum energy

4) House Robber ⭐⭐⭐

🧩 Algorithm

dp[i] = max(
   take current + dp[i-2],
   skip current + dp[i-1]
)

βœ… Smart Steps

  • state = house index
  • choices = rob / skip
  • no adjacent allowed
  • classic take-not-take DP

5) Unique Paths ⭐⭐

🧩 Algorithm

dp[i][j] = dp[i-1][j] + dp[i][j-1]

βœ… Smart Steps

  • state = cell (i,j)
  • move = up + left reverse thinking
  • answer = ways from top-left

🟑 MEDIUM DP TOPICS (Pattern Based)

Goal: Learn reusable interview patterns


πŸ”Ή PATTERN 1: TAKE / NOT TAKE

6) Subset Sum ⭐⭐⭐

🧩 Algorithm

dp[i][target] = take || notTake

βœ… Smart Steps

  • state = index + target
  • choice = include current / exclude
  • base = target == 0

7) 0/1 Knapsack ⭐⭐⭐

🧩 Algorithm

dp[i][W] = max(
   value[i] + dp[i-1][W-weight[i]],
   dp[i-1][W]
)

βœ… Smart Steps

  • state = item + remaining capacity
  • choices = pick / skip
  • answer = maximum profit

8) Coin Change ⭐⭐⭐

🧩 Algorithm

ways = take same coin + skip coin

βœ… Smart Steps

  • if infinite use β†’ stay on same index
  • if single use β†’ move next index

πŸ”Ή PATTERN 2: STRING DP

9) LCS ⭐⭐⭐

🧩 Algorithm

if s1[i]==s2[j]
   1 + dp[i-1][j-1]
else
   max(dp[i-1][j], dp[i][j-1])

βœ… Smart Steps

  • state = i,j
  • compare both strings
  • match β†’ diagonal
  • no match β†’ max of left/up

10) Edit Distance ⭐⭐⭐

🧩 Algorithm

1 + min(insert, delete, replace)

βœ… Smart Steps

  • state = i,j
  • choices = 3 operations
  • answer = minimum operations

πŸ”Ή PATTERN 3: LIS FAMILY

11) LIS ⭐⭐⭐

🧩 Algorithm

if arr[j] < arr[i]
   dp[i] = max(dp[i], 1 + dp[j])

βœ… Smart Steps

  • state = current index
  • check previous smaller values
  • build longest chain

πŸ”΄ HARD DP TOPICS (Advanced)

Goal: Master state transitions


12) Palindrome Partitioning ⭐⭐⭐

🧩 Algorithm

try every cut position
ans = 1 + solve(nextCut)

βœ… Smart Steps

  • state = start index
  • choice = partition at every valid palindrome
  • answer = minimum cuts

13) Matrix Chain Multiplication ⭐⭐⭐

🧩 Algorithm

for every k in i to j
   cost = left + right + multiplication cost

βœ… Smart Steps

  • state = i,j
  • choice = every partition point
  • answer = minimum multiplication cost

14) Tree DP ⭐⭐⭐

🧩 Algorithm

solve(left) + solve(right)
combine answers

βœ… Smart Steps

  • define answer per node
  • ask what node returns to parent
  • combine child states

15) Bitmask DP (TSP) ⭐⭐⭐

🧩 Algorithm

dp[mask][node]

βœ… Smart Steps

  • state = visited cities + current city
  • choice = visit unvisited city
  • answer = minimum total path

⚑ SMART RECOGNITION TRICKS

βœ… If problem says...

πŸ”Ή Count ways

Use:

  • Fibonacci DP
  • Grid DP
  • Coin change

πŸ”Ή Minimum / Maximum

Use:

  • Knapsack
  • Frog jump
  • Path sum

πŸ”Ή Subsequence

Use:

  • Take / not take DP
  • LCS family

πŸ”Ή Partition

Use:

  • MCM
  • Palindrome DP
  • Burst balloons

🎯 FAST INTERVIEW SOLVING TEMPLATE

1. Write recursion first
2. Identify repeated states
3. Add memoization
4. Convert into tabulation
5. Optimize memory

πŸ† FINAL MUST MASTER ORDER

Fibonacci
β†’ Climbing stairs
β†’ Frog jump
β†’ House robber
β†’ Subset sum
β†’ 0/1 knapsack
β†’ LCS
β†’ LIS
β†’ MCM
β†’ Tree DP
β†’ Bitmask DP

πŸš€ This format is made for quick revision + algorithm-first understanding, so you can directly convert every topic into code easily.