DSA
overlapping subproblems
the same call recurs (the waste DP removes)
Source board
This definition comes from the board below. Open it to see the term in context.
Recursion and Dynamic ProgrammingDSAMore terms from this board
- base casethe stopping condition
- dynamic programmingrecursion + remembering solved subproblems
- knapsack / edit distance / LCSclassic DP problems
- optimal substructureoptimum built from sub-optima
- 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)