subproblems

Subproblems are smaller instances of a problem that can be solved independently and then combined to form a solution to the original task. They arise when a problem exhibits a recurring structure, allowing a complex question to be answered by solving several simpler questions whose answers can be merged.

Two properties are often discussed in algorithm design: optimal substructure and overlapping subproblems. Optimal substructure means that an optimal solution to the overall problem can be built from optimal solutions to its subproblems. Overlapping subproblems occur when the same subproblems appear multiple times, enabling reuse through techniques such as memoization or dynamic programming. When these properties hold, breaking the problem into subproblems can dramatically reduce computational effort.

Practical approaches include recursion, where a problem is solved by solving subproblems, and dynamic programming, which stores results to avoid recomputation. Classic examples include computing Fibonacci numbers, where the answer depends on smaller subproblems; the knapsack problem, where the best value for a weight limit depends on subproblems with smaller limits; and path-finding or matrix chain multiplication problems solved in a bottom-up fashion.

Not all problems have these properties; some lack optimal substructure or exhibit non-reusable subproblems, in which case other strategies may be needed. Nevertheless, recognizing subproblems is a central idea in problem solving and algorithm design, enabling modular reasoning, result reuse, and potential parallelization.