Dynamic Programming: Knapsack, Paths and LIS Families | DSA Interview Patterns - Study Chapter | QuizMaker

Design DP state, transition, base case, and answer extraction before writing code.

Read: 22m
Type: Chapter
Access: Free

Course

DSA Interview Patterns Roadmap

Topic

Dynamic Programming

Learning Outcome

Design DP state, transition, base case, and answer extraction before writing code.

Pattern Recognition

Item	Detail
Core signal	The problem asks for best/count/possible over choices and brute force repeats the same subproblems.
Use when	You can describe the remaining problem with a small state tuple.
Avoid when	The required invariant is not monotonic or the input constraints point to a simpler direct scan.

Intuition

DP is cached recursion: first define what the function means, then optimize storage later.

Exact Practice Question Names

Climbing Stairs
Coin Change
Coin Change II
Word Break
Unique Paths
Dungeon Game
Partition Equal Subset Sum
Longest Increasing Subsequence

Interview Approach

Write the recursive meaning of dp state.
Identify choices and transition.
Set base cases for impossible and complete states.
Memoize, then convert to tabulation if useful.
Compress space only after correctness is clear.

Pseudocode

dp[state] = answer for this remaining subproblem
for each valid choice from state:
  candidate = combine(choice, dp[next_state])
  dp[state] = best/count/or of candidates
return dp[start_state]

Sample Dry Run

In coin change, dp[amount] is the fewest coins for that amount. dp[11] checks 1 + dp[10], 1 + dp[9], and 1 + dp[6] for coins [1,2,5].

Edge Cases

Impossible states
Zero amount
Order matters vs does not matter
Subsequence vs subarray

Common Mistakes

Coding a table before defining state
Double counting combinations as permutations
Compressing space in the wrong loop order

Complexity

Item	Detail
Expected time	Depends on states times transitions; commonly O(n*target), O(mn), or O(n log n) for optimized LIS.
Expected space	Number of states, sometimes compressible.

Java, C++ and Python Notes

Java: prefer explicit classes and clear helper methods over clever one-liners.
C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.

Quick Revision Checklist

Name the pattern before coding.
State the invariant or DP state in one sentence.
Dry-run the smallest non-trivial example.
Close with time and space complexity.