Skip to main content

Courses About Pricing Educators

Sign in Get started

Courses About Pricing Educators

Get started Sign in

Loading courses

Loading lessons

Dynamic Programming: Data Structures and Algorithms: Uncharted

Courses Data Structures and AlgorithmsDynamic Programming

Dynamic ProgrammingPro

Name reusable subproblems, remember their results, and build tables for classic choices.

Data Structures and Algorithms
Unit 13 of 16
20 lessons
130 min
420 XP

This unit is part of Pro. Upgrade to open every lesson in it.

Lessons

20 total

1Remember or RepeatDefine reusable subproblem state and choose memoization or tabulation to avoid repeated work.ProInteractiveConcept6 min20 XPOpen
2Fib, Three WaysApply naive memoized and bottom-up Fibonacci comparison to comparing naive recursion, memoization, and bottom-up state through call counters.ProCodeConcept6 min20 XPOpen
3Climbing StairsApply one-or-two-step bottom-up recurrence to counting routes whose final move came from one or two stairs below.ProCodeConcept6 min20 XPOpen
4Predict the TableFill a dynamic-programming table in dependency order from explicit state meaning and base cases.ProInteractiveConcept6 min20 XPOpen
5Min-Cost StairsApply minimum-cost take-one-or-two recurrence to choosing the cheaper of the previous two paid steps.ProCodeConcept6 min20 XPOpen
6The Two QuestionsTest whether a problem has overlapping subproblems and a valid composition from smaller optimal answers.ProInteractiveConcept6 min20 XPOpen
7House RobberApply take-or-skip rolling recurrence to choosing take or skip while carrying the best non-adjacent total forward.ProCodeConcept6 min20 XPOpen
8Fewest CoinsApply bottom-up minimum-coin table to making exact change with a minimum-count table.ProCodeConcept6 min20 XPOpen
9Coin DrillsApply reuse one coin-change table for many amounts to answering several exact-change amounts from one reusable table.ProCodePractice8 min20 XPOpen
10Grid PathsApply row-by-row path-count table to accumulating ways into each city-grid corner from above and left.ProCodeConcept6 min20 XPOpen
11Min Path SumApply top-and-left minimum-cost grid table to accumulating the cheaper of the top and left route into every weighted cell.ProCodeConcept6 min20 XPOpen
12From Memo to TableApply equivalent memoized and tabulated recurrence to expressing the same Fibonacci recurrence with a cache and an ordered table.ProCodeConcept6 min20 XPOpen
13The Space SqueezeApply two-variable rolling DP state to discarding older stair states once only two predecessors remain useful.ProCodeConcept6 min20 XPOpen
14Longest Common ThreadApply two-string longest-common-subsequence table to following a shared subsequence through two strings as a diff would.ProCodeConcept6 min20 XPOpen
15Edit DistanceApply insert-delete-replace distance table to counting the inserts, deletes, and replacements behind an autocorrect guess.ProCodeConcept6 min20 XPOpen
16Subset Sum, LiteApply reachable-sums set DP to tracking which target totals are reachable after each value.ProCodeConcept6 min20 XPOpen
17Knapsack PackingApply reverse-capacity zero-one knapsack to maximizing carry-on value without reusing a packed item.ProCodePractice8 min20 XPOpen
18Longest Rising RunApply quadratic predecessor DP to extending the best increasing subsequence ending at every position.ProCodePractice8 min20 XPOpen
19Explain the RecurrenceSpecify a DP state, base case, transition, unreachable condition, and evaluation order.ProInteractiveConcept6 min20 XPOpen
20Dynamic Programming Mastery CheckApply minimum-count and combination-count table synthesis to computing minimum coin count and combination count from two related tables.ProCodeMastery check10 min40 XPOpen

Weighted Graphs and Union-Find Greedy and Backtracking