dptable

Given an array $cost$ of length $N=6$. Find the minimum total cost to reach index $N-1$, starting from index $0$. At each step you can jump $1$ or $2$ positions forward, paying $cost[j]$ when you land on index $j$.

Base case: $dp[0] = 0$. We start at index $0$ with zero cost (we are already here).

$dp[1]$: only reachable from index $0$. Cost $= dp[0] + cost[1] = 0 + 3 = 3$.

$dp[2]$: from index $0$: $0 + 2 = 2$; from index $1$: $3 + 2 = 5$. Best: $\min(2, 5) = 2$.

$dp[3]$: from index $1$: $3 + 6 = 9$; from index $2$: $2 + 6 = 8$. Best: $\min(9, 8) = 8$.

$dp[4]$: from index $2$: $2 + 1 = 3$; from index $3$: $8 + 1 = 9$. Best: $\min(3, 9) = 3$.

$dp[5]$: from index $3$: $8 + 4 = 12$; from index $4$: $3 + 4 = 7$. Best: $\min(12, 7) = 7$.

$dp[5] = 7$. Optimal path: $0 \to 2 \to 4 \to 5$ with total cost $0 + 2 + 1 + 4 = 7$.