DSA
dynamic programming
recursion + remembering solved subproblems
Source board
This definition comes from the board below. Open it to see the term in context.
Recursion and Dynamic ProgrammingDSAAlso defined on Algorithm Design Patterns.
More terms from this board
- base casethe stopping condition
- knapsack / edit distance / LCSclassic DP problems
- optimal substructureoptimum built from sub-optima
- overlapping subproblemsthe same call recurs (the waste DP removes)
- recurrencehow a state depends on smaller states
- recursiona function calling itself on a smaller input
- recursion treethe tree of calls
- rolling arraykeep only the recent rows to cut space
- statethe parameters identifying a subproblem
- tabulationbottom-up table fill
- time#states × work/state
- ViterbiDP over sequences (ML/bio)