How do you know a problem is dynamic programming?

The two conditions that make it dynamic programming

Two properties must both hold. Optimal substructure means an optimal solution to the whole is composed of optimal solutions to smaller instances of the same problem, so an optimum can be assembled from subproblem optima. Note what this does not say: you still have to enumerate the competing transitions and take the best of them. Being able to commit to one locally optimal choice without exploring the alternatives is the stronger greedy-choice property, and conflating the two is a common slip. Overlapping subproblems means the naive recursion reaches the same smaller instance many times along different paths.

The practical test is to write the brute-force recursion first and ask what its parameters are. If the recursion branches but the parameter space it visits is small relative to the number of paths, the same states are being recomputed and caching collapses the exponential into a polynomial. If each call reaches a genuinely fresh state there is nothing to cache and this is backtracking; if one locally optimal choice can be proven safe without exploring the alternative, it is greedy.

Take 0/1 knapsack: n items with weights and values, a capacity W, maximise value with each item used at most once. The recursion at each item chooses take or skip, so there are 2^n paths, but any path is fully described by how many items remain and how much capacity remains. That is n × W distinct states reached by 2^n paths, which is the overlap that makes it a dynamic programming problem.

Defining the state

A state is the minimum set of parameters such that the answer from that point onwards is fully determined, independent of how you arrived. That independence is the whole requirement: if two histories reach the same parameter tuple but need different answers, the state is under-specified and the memo table returns wrong results rather than merely slow ones.

For knapsack, define solve(i, c) as the best value obtainable from items i onwards with c capacity left. Which items you already took is deliberately not part of the state, because their effect is already summarised in c. Recognising what can be summarised away is the actual skill, and it is why candidates who start by naming the state usually finish while candidates who start writing loops usually stall.

The recurrence follows directly, and the base case is the state where no decisions remain:

private int solve(int i, int c) {
    if (i == n) return 0;                          // no items left, nothing more to gain
    if (memo[i][c] != -1) return memo[i][c];

    int best = solve(i + 1, c);                    // skip item i
    if (weight[i] <= c) {                          // take it only if it fits
        best = Math.max(best, value[i] + solve(i + 1, c - weight[i]));
    }
    return memo[i][c] = best;
}

Converting to a table

Tabulation is the same recurrence with the recursion stack replaced by loops, and two mechanical steps get you there. The memo array becomes the table, with the same dimensions as the state space. Then the loops must visit states so that every state a cell depends on is already filled, which means iterating in the reverse of the dependency direction. Here solve(i, ·) reads only solve(i + 1, ·), so i runs downwards from n - 1.

int[][] dp = new int[n + 1][W + 1];                // dp[n][*] = 0 is the base case

for (int i = n - 1; i >= 0; i--) {                 // downwards: row i reads row i+1
    for (int c = 0; c <= W; c++) {
        dp[i][c] = dp[i + 1][c];
        if (weight[i] <= c) {
            dp[i][c] = Math.max(dp[i][c], value[i] + dp[i + 1][c - weight[i]]);
        }
    }
}
return dp[0][W];

Complexity is states multiplied by the cost of one transition: O(n·W) time, O(n·W) space. Phrase it that way rather than reading it off the loops, because it is the formulation that survives when the transition is not O(1).

Because row i only ever reads row i + 1, the table collapses to a single array:

int[] dp = new int[W + 1];
for (int i = n - 1; i >= 0; i--) {
    for (int c = W; c >= weight[i]; c--) {         // descending, and this is not optional
        dp[c] = Math.max(dp[c], value[i] + dp[c - weight[i]]);
    }
}
return dp[W];

The trap

The descending inner loop is where strong and adequate answers separate, and the weak version of the answer is "you iterate backwards for 0/1 knapsack" recited as a rule. The reason is that dp[c] must read dp[c - weight[i]] as it stood for the previous item, since taking item i is only legal once. Descending c means every index below c is still holding the previous row's value when it is read. Ascending would read a cell already overwritten for item i, which permits taking the same item twice, and that is precisely the unbounded knapsack recurrence rather than a bug in an obscure sense.

So the direction is not a memorised quirk. It is a statement about which row of the two-dimensional table each read is meant to hit. The safe move under interview pressure is to write the two-dimensional version, get it correct, state that the compression is available, and only perform it if asked.

What to say out loud

Narrate four steps in order: the brute-force recursion and its branching, the state and why it is sufficient, the recurrence with its base case, then the tabulation with its loop direction justified. That sequence is itself the signal being graded, because it is the procedure that transfers to a problem you have never seen.

Define the state before writing any loop, and derive the loop direction from which states the recurrence reads. Every dynamic programming bug that is not an off-by-one is one of those two things done by feel.