Fibonacci-style, house robber, climbing stairs, and linear DP patterns.
1D DP problems have a single state variable, usually dp[i] representing the answer for the first i elements. The recurrence typically looks at dp[i-1] or dp[i-2].
O(n)
O(n) reducible to O(1) for Fibonacci-like problems
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
dp[i] = dp[i-1] + dp[i-2]
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
dp[i] = cost[i] + min(dp[i-1], dp[i-2])
dp[i] = dp[i-1] (if valid single) + dp[i-2] (if valid pair)
track max and min due to sign flips
dp[i] = min(dp[i - coin] + 1) for all coins