Define a DP state before the recurrence
Dynamic programming reuses overlapping subproblem results. A state must retain every fact needed for later decisions; omitting capacity, position or previous choice can merge incompatible situations. Specify base cases, transition, evaluation order and answer location. Top-down memoization and bottom-up tabulation are ways of evaluating the same valid recurrence. Compress storage only after identifying which previous states remain needed.
Greedy needs a correctness argument
A greedy method makes a local choice that must be extendable to an optimum. For unweighted interval scheduling, an exchange argument shows that the earliest-finishing compatible interval can replace an optimal first interval without reducing remaining opportunity. Adding weights breaks that objective and may require DP. A collection of successful examples is useful testing, but not a proof that the local choice is always safe.
Backtracking explores a decision tree
Backtracking builds a partial solution, tests or extends it, and undoes the choice before the next branch. Pruning can save work but needs a reason that every pruned branch cannot produce a required answer. Subset generation has exponential output; a small recursion stack does not make total output space small. Duplicate inputs require a uniqueness policy, often sorting and skipping equivalent choices at a given depth.
Worked Java example
Illustrative snippet: imports, surrounding types or collaborators may be omitted. Read the assumptions before adapting it.
int[] best = new int[capacity + 1];
for (int i = 0; i < weights.length; i++) {
for (int w = capacity; w >= weights[i]; w--) {
best[w] = Math.max(best[w],
best[w - weights[i]] + values[i]);
}
}Walkthrough
This 0/1 knapsack formulation assumes nonnegative integer capacity, positive item weights, compatible arrays and values that fit int. Descending w reads a smaller-capacity value from the previous item stage. Ascending w could read a value already improved by this same item and reuse it, changing the problem to an unbounded variant.
Practice it yourself
Use one item of weight two and value three with capacity four. Compare the descending and ascending updates.
Check your reasoning
Descending updates best[4] from an earlier-stage best[2] of zero, so the answer is three. Ascending sets best[2] to three and later reuses it for best[4] = six, incorrectly selecting the single item twice in the 0/1 problem.
Recall checklist
- Explain the main invariant or contract without looking.
- Trace the example and test an edge case.
- State time, space, input variables and assumptions where relevant.
- Explain one alternative and when you would choose it.