Cosmic Module

D

Qubits of DPK

January 18, 2026

Core DSA
For every problem, you write:
1️⃣ Idea
→ “What am I trying to decide at each step?”
2️⃣ DP State
→ “What info uniquely identifies a subproblem?”
3️⃣ DP Expression
→ “If I’m here, what choices do I have?”
4️⃣ Base Condition
→ “When can I answer immediately?”
5️⃣ Recursion
→ Raw, ugly, exponential — allowed
6️⃣ Memoisation
→ Same recursion + cache
7️⃣ Tabulation
→ Flip recursion into loops
8️⃣ 1D Optimization
→ Only if state allows it

Universal DP Demo Template :

Problem Skeleton (Fill This First)

  • Given:
  • Asked:
  • Constraints:
Before DP: confirm this is NOT greedy / math / two pointers.

1️⃣IDEA

What am I trying to decide at each step?
“At each step, I must decide ______.”
Examples:
  • pick / not pick an element
  • place / skip
  • extend / break
  • take current / move ahead
Mental check:
If you can phrase the problem as binary or finite choices → DP confirmed.

2️⃣DP STATE

What info uniquely identifies a subproblem?
dp[ _____ ][ _____ ]
Explain in words:
  • dp[i][...] → I am at index i
  • dp[...]→ I have remaining x / achieved x
Rule:
State must be:
  • minimal
  • sufficient
  • independent of path taken

3️⃣DP EXPRESSION (CHOICES)

If I’m here, what choices do I have?
Write in plain English first:
  • Choice 1 → ______
  • Choice 2 → ______
  • (Optional) Choice 3 → ______
Then convert to math:
dp[state] =
combine(
choice1 → dp[next_state1],
choice2 → dp[next_state2]
)
Golden Rule:
Every DP transition must reduce the problem size.

4️⃣BASE CONDITION

When can I answer immediately?
Common bases:
  • index == 0 / n
  • sum == 0
  • capacity == 0
  • no items left
Write explicitly:
If ______ → return ______
Interview trap:
Wrong base condition = WA even if logic is correct.

5️⃣RECURSION (RAW, UGLY, ALLOWED)

Can I write the brute-force recursive logic?
Rules:
  • No DP array
  • No optimization
  • Just correctness
Skeleton:
solve(i, state):
if base → return
try all choices
return best answer
Purpose:
This step proves you actually understand the problem.

6️⃣MEMOISATION

Which subproblems repeat?
  • Add dp[][] cache
  • Before computing:
if dp[state] != -1 → return dp[state]
Checkpoint:
Time drops from exponential → polynomial.

7️⃣TABULATION

How do I flip recursion into loops?
Steps:
  1. #
    Decide loop order from recursion dependency
  2. #
    Initialize base states
  3. #
    Fill table bottom-up
Template:
for state1:
for state2:
dp[state] = ...
Loop direction matters
(0/1 vs Unbounded vs Sequence DP).

8️⃣1D OPTIMIZATION (ONLY IF POSSIBLE)

Does dp[i] depend only on dp[i-1]?
If yes:
  • Compress dp[i][*] → dp[*]
  • Decide loop direction:
Rule:
Never force 1D.
Correct 2D > wrong 1D.

FINAL CHECKLIST (TOPPER SELF-TEST)

Ask yourself:
  • Can I explain state in one sentence?
  • Can I derive transitions without code?
  • Can I justify loop direction?
  • Can I convert this to recursion again if needed?
If yes → you own the DP

Chamber Portal

Database for DP questions