Dynamic Programming Part 1
Dynamic Programming (DP) is a technique to optimize recursive solutions by storing intermediate results to avoid repeated work. It is applied to problems with overlapping subproblems and optimal substructure, meaning solutions to subproblems can be reused and combined for the overall solution. Part 1 covers fundamental DP patterns including basic recurrences and knapsack problems.
This pattern introduces DP with simple problems like computing Fibonacci numbers or climbing stairs. A naive recursive solution recalculates many subproblems, leading to exponential time. DP (via memoization or bottom-up tabulation) saves results and runs in linear time.
Example Problems:
Nth Fibonacci NumberClimbing Stairs
Solution Spotlight: Climbing Stairs
This solution uses a bottom-up DP approach for the climbing stairs problem. Instead of naive recursion (which would recompute subproblems), it builds up an array
dp where each entry represents the number of ways to reach that step. The recurrence dp[i] = dp[i-1] + dp[i-2] mirrors the fact that one can arrive at step i from either step i-1 or i-2. By filling this table iteratively, we compute the result in O(n) time without redundant calculations.ClimbingStairs.java
Loading code syntax...