Foundations — DP problems — rod cutting, egg drop, DP on trees

This page assumes you have seen nothing. Before you can read the parent note, you must own every symbol it throws at you. We build them one at a time, each one earned before the next uses it.

0. What is an array, and what does $p[i]$ mean?

An array is just a row of boxes, each holding one number, each labelled by a whole-number position called an index.

• Picture: the red box in the figure is box number $2$; $p[2]$ is whatever number lives there.
• Why the topic needs it: rod cutting stores a price list $p[\mathrm{1..}n]$ where $p[i]$ is the price of a rod-piece of length $i$. Without indexing we could not say "the price of a length-3 piece" in symbols.

1. The notation $1\le i\le n$ and "for all"

• Picture: a number line with a filled bar from $1$ to $n$; every tick inside is an allowed value of $i$.
• Why the topic needs it: every DP recurrence tries many choices — "the first cut could be length $1$, or $2$, ... up to $n$". The range says which choices are legal.

2. $\max$, $\min$, and $\sum$ — the three loops-in-disguise

These three symbols each mean "run through a range and combine the values". They are the beating heart of every formula in the parent.

3. Functions and the notation $r(n)$, $D(e,f)$, $f(v,0)$

• Picture: a box with arrows going in (inputs) and one arrow coming out (the answer).
• Why one input vs. two vs. two-with-a-flag:
  • $r(n)$ — rod revenue depends on one thing: the rod's length.
  • $D(e,f)$ — egg-drop cost depends on two things: eggs left $e$ and floors left $f$. Change either and you have a different subproblem.
  • $f(v,0)$ / $f(v,1)$ — tree value depends on the node $v$ and a yes/no flag ($0$ = "$v$ excluded", $1$ = "$v$ included"). The flag exists because the parent's decision needs to know what the child decided.

4. Recursion and base cases — where the smaller copies come from

• Picture: a staircase of shrinking problems; the bottom red step is the base case that returns an answer directly.
• Why the topic needs it: without a base case the shrinking never stops. Every recurrence in the parent pairs a general rule with base cases — this is required before you meet Recursion and Memoization.

5. Overlapping subproblems and memoization

• Why "bottom-up": if you fill $r[0],r[1],r[2],\dots$ in order, then when you compute $r[j]$ every $r[j-i]$ it needs is already done. No recursion needed — just an ordered fill.

6. Big-O notation $O(n^2)$, $O(n)$ — the cost tag

• Why the topic needs it: the whole point of DP is speed. Rod cutting is $O(n^2)$ (for each of $n$ lengths, try up to $n$ first cuts). Tree DP is $O(n)$ (each edge touched once). You cannot appreciate the win without this tag.

7. Trees, nodes, children, and DFS

• Picture: the red node is the root; arrows point down to its children; the shaded blob is one subtree.
• Why no cycles matters: because there are no loops, each subtree is a separate, independent subproblem — the exact condition DP needs. This connects to Tree Traversal (DFS).

The prerequisite map

Everything on the left builds the machinery; it all funnels into the parent note DP problems. From here you are ready for Dynamic Programming, Recursion and Memoization, Knapsack Problem, and the contrasts with Greedy Algorithms and Binary Search.

Equipment checklist

Cover the right side and see if you can say it out loud.