Subprobleme

Subprobleme are a fundamental concept in problem solving, mathematics and computer science. A subproblem is a smaller or simpler instance of a larger problem, obtained by fixing certain choices or reducing the scope of the original task. Solving the subproblem provides a building block toward the solution of the original problem. In many algorithmic contexts, subproblems are solved recursively: the main problem is decomposed into one or more subproblems of the same form, each solved independently or with further decomposition, and their solutions are combined to produce the final answer.

Subproblems can be overlapping or disjoint. Overlapping subproblems occur when the same subproblems arise multiple times, a situation exploited by dynamic programming and memoization to avoid recomputation. Disjoint subproblems occur when subproblems do not share work, as in divide-and-conquer algorithms.

Common examples include computing Fibonacci numbers (where the same subproblems reappear) and binary search (each subproblem is a distinct half of the search space). Other examples include shortest path computations and matrix multiplication algorithms that break matrices into blocks.

Design principles for effective use of subproblems include defining clear base cases, formulating a recursive or iterative reduction to subproblems, and combining subproblem solutions to form the overall solution. The concept is linked to optimal substructure, where an optimal solution to the original problem can be constructed from optimal solutions of its subproblems, and to problem decomposition as a general strategy in computer science and mathematics.