Decision Framework

Recursion vs DP

Recursion describes the structure. DP keeps the structure but eliminates repeated subcalls by storing each distinct state once. Same recurrence, different cost.

RecursionBranching

DPCompression

Plain Recursion

Walks a tree of calls. Duplicate subcalls appear across branches.

DP Upgrade

Stores each state once and reuses it. The tree collapses into a table.

Recursion (Active Path)

F(8)

call index0/66

DP (Fill Frontier)

dp[0] = dp[0] + dp[0] = 0 + 0

dp[0]0

dp[1]?

dp[2]?

dp[3]?

dp[4]?

dp[5]?

dp[6]?

dp[7]?

dp[8]?

fill index0/8

DP removes repeated subcalls by caching states

Loading Lab...

Decision Framework

Recursion vs DP

Recursion describes the structure. DP keeps the structure but eliminates repeated subcalls by storing each distinct state once. Same recurrence, different cost.

RecursionBranching

DPCompression

Plain Recursion

Walks a tree of calls. Duplicate subcalls appear across branches.

DP Upgrade

Stores each state once and reuses it. The tree collapses into a table.

Recursion (Active Path)

F(8)

call index0/66

DP (Fill Frontier)

dp[0] = dp[0] + dp[0] = 0 + 0

dp[0]0

dp[1]?

dp[2]?

dp[3]?

dp[4]?

dp[5]?

dp[6]?

dp[7]?

dp[8]?

fill index0/8

DP removes repeated subcalls by caching states

Recursion Vs Dp

Recursion Vs Dp

Recursion vs DP

Plain Recursion

DP Upgrade

Recursion vs DP

Plain Recursion

DP Upgrade