Dynamic Programming Introduction Java | Fresher Interview
Fast recall
Quick revision
Core answer
Whether you can name the two preconditions (overlapping subproblems + optimal substructure) and the two implementation styles
Calling any recursion 'DP', or applying DP without overlapping subproblems (then it's just divide-and-conquer)
Contrast naive O(2^n) Fibonacci with memoized O(n) and name the two preconditions explicitly
Interview-ready guide
Interview answer
Dynamic programming is an optimization technique for problems that break into subproblems, but with two specific properties.
The first is overlapping subproblems, meaning a naive recursive solution would solve the same smaller problem over and over. The textbook example is Fibonacci, where computing fib of n recursively recomputes fib of three, fib of two, and so on, an exponential number of times. The second property is optimal substructure, meaning the optimal solution to the whole problem is built from optimal solutions to its subproblems.
When both properties hold, the core DP idea is to compute each distinct subproblem only once and store its answer, so I never recompute it. That single change collapses exponential recursion into polynomial time. For Fibonacci, the naive version is O of two to the n, but once I store results it becomes O of n.
There are two ways to implement DP. Memoization is top-down: I keep the natural recursion but add a cache, and before computing a subproblem I check whether it's already in the cache. Tabulation is bottom-up: I fill a table starting from the base cases and build up to the answer, often letting me drop space down to constant.
A point I'd make to show understanding is that not every recursion is DP. If the subproblems don't actually overlap, like in merge sort, then there's nothing to cache and it's just divide-and-conquer. So when I approach a DP problem, I first define the state, what dp of i means, then the transition between states, then the base cases.
Dynamic Programming Introduction Java | Fresher Interview
Direct Answer
Dynamic programming (DP) solves problems by breaking them into overlapping subproblems and storing each subproblem's answer so it's computed only once. Use it when the problem has optimal substructure (the optimum is built from sub-optima) and overlapping subproblems (the same subproblem recurs). It turns exponential recursion into polynomial time, via memoization (top-down) or tabulation (bottom-up).
Deep Dive & Architecture
Dynamic programming solves a problem by saving answers to smaller subproblems so the same work is not repeated. It is a good fit when subproblems overlap and a larger answer can be built from smaller answers.
Every DP solution needs four clear parts:
- State: what one saved value means, such as
dp[i] = Fibonacci(i). - Transition: how earlier states create the next one, such as
dp[i] = dp[i-1] + dp[i-2]. - Base cases: known starting values, here
dp[0] = 0anddp[1] = 1. - Order: compute dependencies before the state that uses them.
Worked example: Fibonacci 5
The table grows as 0, 1, 1, 2, 3, 5. A naive recursive solution asks for values such as fib(3) from several branches. DP calculates each index once, reducing exponential repeated work to O(n).
Top-down memoization starts with recursion and caches results only when requested. Bottom-up tabulation fills a table in dependency order. Both commonly use O(n) storage, though Fibonacci needs only the previous two values and can use O(1).
DP is not simply “use an array.” The saved value must have a precise meaning and the transition must cover every valid way to reach it without double-counting or missing cases.
Code Example
// Naive: O(2^n) - recomputes the same subproblems
int fibSlow(int n) { return n < 2 ? n : fibSlow(n-1) + fibSlow(n-2); }
// Memoization (top-down): O(n) - each fib(i) computed once
int fibMemo(int n, Integer[] memo) {
if (n < 2) return n;
if (memo[n] != null) return memo[n];
return memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);
}
// Tabulation (bottom-up): O(n) time, O(1) space
int fibTab(int n) {
if (n < 2) return n;
int a = 0, b = 1;
for (int i = 2; i <= n; i++) { int c = a + b; a = b; b = c; }
return b;
}
Common Mistakes & Pitfalls
- Calling all recursion DP: DP specifically requires overlapping subproblems.
- No overlap: if subproblems don't repeat, you don't need caching - it's divide-and-conquer.
- Wrong state definition: a bad
dp[i]meaning leads to incorrect transitions - define state first. - Ignoring base cases: tabulation must seed the table; memoization must have a base return.
Check your understanding
Answer these without looking back at the article.
- What is memoization vs tabulation in DP and which should you use in interviews?
- How do you solve the coin change problem using dynamic programming?
- What is the longest common subsequence (LCS) problem?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.