Discover published sets by community

A method for solving complex problems by breaking them down into simpler subproblems. It is applicable when the problem can be divided into overlapping subproblems that can be solved independently.

An optimization technique used to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

A property that a problem has if an optimal solution to the problem contains within it optimal solutions to subproblems. For instance, the shortest path problem has this property since a shorter path can be extended to a shorter path in the larger graph.

An algorithm that computes the shortest paths from a single source vertex to all other vertices in a weighted graph. It is capable of handling graphs with negative weight edges and can detect negative weight cycles.

A property of a problem that allows it to be broken down into subproblems that are reused several times. For example, in Fibonacci sequence computation, the calculation of $F(n)$ involves the repetitive calculation of $F(n-1)$ and $F(n-2)$ which are overlapping subproblems.

In dynamic programming, a 'state' represents the current situation of a problem. This is often a combination of various parameters that can define the solution at that point. For instance, in the knapsack problem, a state could be defined by the current weight and the set of items considered.

Also known as Tabulation, it is a dynamic programming approach where the solution is built starting with the smallest subproblems and combining them to solve larger subproblems. This method iteratively fills a table (commonly a multidimensional array).

Transition defines how to move from one state to another state in dynamic programming. In the context of a grid-based problem, the transition might be moving to an adjacent cell with a cost or condition associated with the move.

A mathematical description of the operation of a dynamic programming algorithm, usually defined in terms of itself. For instance, the recurrence for the Fibonacci sequence is $F(n) = F(n-1) + F(n-2)$, with base cases $F(0) = 0$ and $F(1) = 1$.