Dynamic Programming: Basics
Dynamic programming: states, transitions, the base case — the staircase and the maximum subarray.
Dynamic programming (DP) is a method for problems that break into overlapping subproblems: solve each subproblem ONCE and memorize the answer.
The three-question recipe:
1. State: what is dp[i]? (in words, precisely!)
2. Transitions: how is dp[i] expressed through smaller states?
3. Base: what are the smallest states equal to?
The hello-world of DP is the staircase: you stand at the bottom of a staircase with n steps and climb 1 or 2 steps at a time. How many ways are there to get to the top?
• dp[i] — the number of ways to reach step i;
• step i is reached from steps i-1 or i-2, so dp[i] = dp[i-1] + dp[i-2];
• base: dp[0] = 1 (standing at the bottom), dp[1] = 1.
The staircase. Enter n up to 80, for example: 10
For n = 10 the answer is 89 — these are the Fibonacci numbers, growing out of the problem all by themselves.
Two styles of writing DP:
• tabular (as above): fill the array from the base upward;
• memoization: write the recursion and cache the answers. Which is more convenient is a matter of taste; the complexity is the same.
The second classic — the maximum subarray sum (Kadane's algorithm). State: dp[i] — the maximum sum of a subarray ENDING at i. Transition: either extend the previous subarray or start a new one at a[i].
The maximum subarray. Enter: 8, then -2 1 -3 4 -1 2 1 -5
The answer on the example: 6 (the subarray 4 -1 2 1). Notice: the dp array collapsed into a single variable cur — that often happens when the transition only looks at the previous state.
Task: solve the "staircase" where stepping on certain steps is forbidden (dp[i] = 0 for the forbidden ones). And think how the problem changes with steps of 1, 2 and 3.
Mark the lesson as completed — Level 4 is done. Advanced DP is ahead!