Discover published sets by community

A method for solving complex problems by breaking them down into simpler subproblems, storing the solutions of subproblems to avoid redundant computations. Example: Fibonacci sequence calculation.

In dynamic programming, this refers to the way in which one defines the set of parameters that uniquely determines the subproblems. Example: In knapsack problem, the state could be defined by the current capacity and the number of items considered.

A property of a problem that indicates the optimal solution can be constructed from optimal solutions of its subproblems. Example: The shortest path between two nodes in a graph can be found by combining the shortest paths from the individual segments.

In dynamic programming, it is a formula or a set of rules that determines how the solution to a subproblem contributes to the solution of a larger problem. Example: In a grid path-finding DP, transition could be defined by min(path[i-1][j], path[i][j-1]) + cost[i][j].

A bottom-up dynamic programming technique where the solution is built starting with the smallest subproblems, filling up a table based on previous answers and returning the last entry as the solution. Example: Iteratively computing Fibonacci numbers in an array, from base cases up.

Not always applicable in DP, it's a property where locally optimal solutions can lead to a global optimum. In DP, it can sometimes simplify the problem if combined with optimal substructure. Example: Coin change problem where using the largest denominations first can simplify the problem.

The process of determining the time and space efficiency of a dynamic programming algorithm. It often involves multiplying the number of subproblems by the time taken to solve each one. Example: The time complexity of a tabulated Fibonacci sequence is O(n).

An approach in dynamic programming where results of expensive function calls are saved, avoiding redundant calculations by returning the cached result when the same inputs occur again. Example: Storing Fibonacci numbers in an array after calculating them.