Climbing Stairs
Each position depends on the previous two positions, so keep only the last two counts and build forward iteratively.
Return how many distinct ways there are to reach the top if you can climb 1 or 2 steps at a time.
Tagged with dynamic-programming
5 cards
Coin Change
Initialize a DP array with an impossible sentinel value, set dp[0] to zero, and for each amount try every coin to update the cheapest reachable solution.
Given coin denominations and a target amount, return the minimum number of coins needed to make that amount or -1 if it is impossible.
Fibonacci
Track only the previous two numbers and iterate until you reach n. This keeps the solution clear and avoids exponential recursion.
Return the nth Fibonacci number.
House Robber
Track the best result when including or excluding the current house. A rolling two-variable DP solution keeps the implementation compact.
Return the maximum amount you can rob from houses without robbing adjacent houses.
Maximum Subarray
Track the best subarray ending at the current position and reset only when starting fresh is better than extending the previous run.
Return the largest possible sum of a contiguous subarray.