1D DP
Apply DP to linear problems. House Robber, Boredom, and Consecutive Subsequence. Each problem uses a 1D state array.
Lessons
1. Intro
One state variable
2. From Memoization to Problems
The transition
3. DP Pattern and Importance
The four-step blueprint
4. LeetCode 198 House Robber - Problem Statement
The classic problem
5. LeetCode 198 House Robber - Why Greedy Fails
Why odd/even sums fail
6. LeetCode 198 House Robber - Defining the DP
Setting up the state
7. LeetCode 198 House Robber - Transition
The take-or-skip choice
8. LeetCode 198 House Robber - Base Cases
Starting conditions
9. LeetCode 198 House Robber - Final Answer
Reading the answer
10. LeetCode 198 House Robber - Implementation
Putting it together
11. Quiz: House Robber State
Testing DP state design
12. Lessons from House Robber
summary
13. Codeforces 455A Boredom - Problem Statement
A similar structure
14. Codeforces 455A Boredom - Defining the DP
First 1D DP problem
15. Codeforces 455A Boredom - Transition
Take or skip each value
16. Codeforces 455A Boredom - Base Cases
Starting conditions
17. Codeforces 455A Boredom - Final Answer
Reading the answer
18. Codeforces 455A Boredom - Implementation
Complete solution
19. Quiz: Boredom Reduction
Testing problem reduction
20. Codeforces 977F Consecutive Subsequence - Problem Statement
Large values, same pattern
21. Codeforces 977F Consecutive Subsequence - State Definition - 1
Learn how to define the DP state for finding the longest consecutive subsequence.
22. Codeforces 977F Consecutive Subsequence - State Definition - 2
Extra requirements for state definition.
23. Codeforces 977F Consecutive Subsequence - Transition
Learn the transition formula: extend subsequences by linking consecutive values.
24. Codeforces 977F Consecutive Subsequence - Base Cases
Learn how to initialize the DP values before processing the array elements.
25. Codeforces 977F Consecutive Subsequence - Final Answer and Reconstruction
Learn how to find the answer and rebuild the subsequence
26. Codeforces 977F Consecutive Subsequence - Implementation
Putting it all together
27. Quiz: Consecutive Subsequence
Testing LIS variant
28. Vocabulary - State Compression
Reducing DP dimensions
29. Lessons from Boredom and Consecutive Subsequence
Patterns from both problems
30. Pattern - Adjacent Blocking
The common structure
31. Challenge: Trace Boredom
Manual DP exercise
32. Quiz: 1D DP Patterns
Test your understanding
33. Codeforces 1741E Sending a Sequence - Problem Statement
Understand the block cutting problem where each block has a length marker
34. Codeforces 1741E Sending a Sequence - From Intuition to Prefix States
From intuition to states
35. Codeforces 1741E Sending a Sequence - Defining the State and Base Case
Learn how to define the DP state using prefix arrays
36. Codeforces 1741E Sending a Sequence - Determining the Final Answer
Learn how to extract the final answer from the DP state
37. Codeforces 1741E Sending a Sequence - Transition Case 1
Right End Block
38. Codeforces 1741E Sending a Sequence - Transition Case 2
Left End Block
39. Practice - Maximum Points
Apply the pattern
40. What's Next
Preview of 2D DP
41. Section Recap
What you learned and what comes next
Practice Problems
Classic take/skip pattern where you decide whether to take all instances of a number or skip it
Extends Frog 1 with variable jump length K - teaches handling multiple transitions per state.
DP with greedy construction, teaches state optimization on linear arrays
Classic coin-change variant teaching maximization in 1D DP
Greedy-DP hybrid teaching when left/right decisions create 1D DP
Direct application of house robber pattern with frequency counting twist
Index-based recursion and decision making converge in one foundational DP problem
Finds the longest consecutive-value subsequence with DP and reconstructs it.
1D DP on character arrays with constraint-based transitions
Linear DP after sorting, teaches preprocessing for state optimization