Intro

In "1D (one-dimensional) DP (Dynamic Programming)", your state depends on one variable. This is the simplest form of dynamic programming. That variable is usually:

• Position: $dp[i] = \text{answer considering elements }0\text{ to } i$
• Value: $dp[v] = \text{answer for value }v$

You already know 1D DP from the previous section: Fibonacci uses $dp[n]$, Climbing Stairs uses $dp[i]$, House Robber uses $dp[i]$. All of these have a single index. Later sections will introduce 2D (two-dimensional) DP (two variables like $dp[i][j]$) and beyond.

For now, you focus on problems where one index is enough.