Dynamic Programming and Algorithms Review

A collection of vocabulary flashcards based on core concepts in dynamic programming and related algorithms.

Dynamic Programming

A method used for solving complex problems by breaking them down into simpler subproblems and storing the results.

Cache (Memoization)

An array used to store the results of subproblems to avoid redundant computations.

Overlapping Sub-Problems

A characteristic of a problem where the solution to a subproblem is needed multiple times.

Optimal Sub-Structure

A property where the optimal solution of a problem can be constructed from optimal solutions of its subproblems.

1D Dynamic Programming

Refers to dynamic programming solutions that use a single loop for iteration.

Fibonacci Sequence

A sequence defined by F(n) = F(n-1) + F(n-2), with F(0) = 0 and F(1) = 1.

Time Complexity

A computational complexity that describes the amount of time an algorithm takes to complete as a function of the length of the input.

Greedy Algorithm

An algorithm that builds up a solution piece by piece, always choosing the next piece that offers the most immediate benefit.

Knapsack Problem

An optimization problem that involves selecting a set of items with given weights and values to maximize total value without exceeding weight capacity.

Universal Change Making Problem

A problem that generalizes the coin change problem with arbitrary coin denominations.