Recursion & Backtracking

{title}

{title} connects recursion to dynamic programming by caching answers for repeated states instead of recomputing the same subtree.

Topic

Recursive DP

Pattern

Memoized Recursion

Time

O(unique states x transition cost)

Space

O(unique states + depth)

Call tree simulation

initial state

depth 0

choice

state

choice

cache hit

choice

compute

choice

store

Code Tracker

:::

1int solve(state) {

2 if (base(state)) return value;

3 if (memo.has(state)) return memo[state];

4 int ans = best(next states);

5 return memo[state] = ans;

Loading Lab...

Recursion & Backtracking

{title}

{title} connects recursion to dynamic programming by caching answers for repeated states instead of recomputing the same subtree.

Topic

Recursive DP

Pattern

Memoized Recursion

Time

O(unique states x transition cost)

Space

O(unique states + depth)

Call tree simulation

initial state

depth 0

choice

state

choice

cache hit

choice

compute

choice

store

Code Tracker

:::

1int solve(state) {

2 if (base(state)) return value;

3 if (memo.has(state)) return memo[state];

4 int ans = best(next states);

5 return memo[state] = ans;

Memoization Basics

Memoization Basics

{title}

{title}