Probability DP
You know deterministic DP. Now handle randomness. Compute probabilities and expected values.
Lessons
1. Intro
What you'll learn
2. Core Concept
Expected values
3. Vocabulary - Expected Value
Average outcome
4. Quiz: Expected Value
Understanding expectation
5. Vocabulary - Transition Probability
Weighted edges
6. The Key Formula
Weighted sum
7. Quiz: Linearity of Expectation
A powerful property
8. LeetCode 688 Knight Probability in Chessboard - Problem Statement
LeetCode 688
9. Knight Probability - The Setup
Understanding the grid
10. Knight Probability - State Definition
What dp[r][c][k] means
11. Knight Probability - Transition
Eight directions
12. Knight Probability - Base Cases
Boundaries
13. Knight Probability - Implementation
The code
14. Knight Probability - Walkthrough
Tracing the transitions
15. Lessons from Knight Probability
summary
16. Challenge: Knight Expected Moves
Expected value variant
17. LeetCode 576 Out of Boundary Paths - Problem Statement
LeetCode 576
18. Out of Boundary - State Definition
Position and moves
19. Out of Boundary - Transition
Four directions
20. Out of Boundary - Implementation
The code
21. Out of Boundary - Walkthrough
Counting paths with probability
22. Lessons from Out of Boundary
summary
23. Quiz: Out of Boundary Counting
Counting vs probability
24. LeetCode 808 Soup Servings - Problem Statement
LeetCode 808
25. LeetCode 808 Soup Servings - The Observation
Scaling trick
26. LeetCode 808 Soup Servings - State Definition
Remaining amounts
27. LeetCode 808 Soup Servings - Transition
Four operations
28. LeetCode 808 Soup Servings - Implementation
The code
29. LeetCode 808 Soup Servings - Walkthrough
Understanding the approximation
30. Lessons from Soup Servings
summary
31. Quiz: Soup Approximation
Why the threshold works
32. Pattern - Probability DP
Core idea
33. LeetCode 837 New 21 Game - Problem Statement
Card drawing probability
34. LeetCode 837 New 21 Game - Implementation
Sliding window optimization
35. Quiz: New 21 Game Stopping
Understanding the constraint
36. Random Point in Circle - Problem Statement
Geometric probability
37. Toss Strange Coins - Problem Statement
Probability with different coins
38. Toss Strange Coins - Implementation
Space optimization
39. Dice Roll Simulation - Problem Statement
Constrained sequences
40. Quiz: Dice Roll States
State design choices
41. Challenge: Infinite Expected Value
When expectation diverges
42. Pattern - When to Use Probability DP
Recognizing the pattern
43. What's Next
Preview of D&C Optimization
44. Section Recap
What we learned
Practice Problems
Perfect intro - calculate probability of more heads than tails with different coin probabilities.
Probability that sum of n dice falls in a range - clean transitions.
Expected value with time-based probability transitions.
Game theory + probability with alternating turns.
Classic expected value - random selection until all dishes empty.
Sliding window optimization for probability DP.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Rock-paper-scissors survival. 3D probability DP with transition matrix.
Expected days to collect k distinct orbs. DP on collected count.
Expected people on escalator. Probability DP with time steps.
Minimum changes for valid circular attack. DP on consecutive segments.
Expected inversions in BFS order. Probability DP on tree structure.
Expected days to pass all mirrors. Linear recurrence with restart.
Classic probability puzzle. Recurrence reveals beautiful 0.5 answer.
Count valid distributions. Combinatorics + probability with DP.