DSA
optimal substructure
optimum built from sub-optima
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
- 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)