AlgoFoxGet AlgoFox App

CoursesDynamic Programming

DP Foundations

Lessons
9
Exercises
56
Minutes
59
  1. 1

    Solve Each Subproblem Once

    Naive recursion re-solves the same subproblems exponentially many times — DP caches or tabulates so each is solved exactly once.

    Complete codeMultiple choice
    6 exercises
    5 min
  2. 2

    Climbing Stairs

    Every climb ends with a 1-step or a 2-step — so ways(n) = ways(n-1) + ways(n-2), and your first DP table is Fibonacci in disguise.

    Complete codeDebugMultiple choiceTrace
    6 exercises
    6 min
  3. 3

    N-th Tribonacci Number

    A three-term recurrence: T(n) = T(n-3) + T(n-2) + T(n-1). Rolling three variables replaces the whole table — O(1) space.

    Code orderMultiple choiceTrace
    6 exercises
    6 min
  4. 4

    Min Cost Climbing Stairs

    Your first minimization DP: pay the step, arrive from the cheaper of the two below — and remember the top is reachable from either of the last two steps.

    Complete codeMultiple choiceTrace
    6 exercises
    6 min
  5. 5

    Pascal's Triangle

    Build each row from only the row above: edges are 1, every interior cell sums the two cells overhead — a gentle first taste of 2D DP.

    Complete codeDebugMultiple choiceTrace
    6 exercises
    6 min
  6. 6

    Counting Bits

    dp[i] = dp[i >> 1] + (i & 1): the subproblem arrives by bit shift, proving a DP recurrence doesn't have to look at i-1 and i-2.

    Complete codeMultiple choiceTrace
    6 exercises
    7 min
  7. 7

    DP Foundations CheckpointCheckpoint

    No new concepts — transfer the island's build-from-smaller move to unseen ground: tiling a 2xN strip with dominoes, a frog hopping stones for coins, smooth numbers grown from their own table, and the divisor game's smallest truths.

    Complete codeCode orderMultiple choiceTrace
    6 exercises
    7 min
  8. 8

    DP Foundations ReviewReview

    Mixed recap of the island: define dp[i] in words before anything else, recurrences from the last move, base cases as the smallest truths, memo vs table as two schedules for one definition, rolling variables for O(1) space, and the exponential-vs-linear bill.

    Complete codeCode orderMultiple choice
    6 exercises
    6 min
  9. 9

    Boss: House RobberBoss

    The island's final test: rob a street where adjacent houses trip the alarm. One take/skip recurrence prices every plan at once — and the boss's traps are grabbing the richest house first and locking the loot into odd or even positions.

    Complete codeDebugCode orderMultiple choiceTrace
    8 exercises
    10 min
AlgoFox Pro

Dynamic Programming is part of AlgoFox Pro

You can read the whole course outline here. The exercises are in the app, along with your streak, your mistake review, and the progress that carries across your devices.

Pro starts with a 3 day free trial. The app store decides who is eligible for an introductory offer, and a lapsed subscription does not get another one.

Download AlgoFox on the App StoreGet AlgoFox on Google Play

Already subscribed in the app? Sign in with the same account and Pro works here too. Quick Play and Battle are free on the web, and so is the first course in every subject.