Counting Numbers (Digit DP)
Learn Counting Numbers (Digit DP) (Dynamic Programming, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Counting Numbers in [0, N] With a Property, Digit by Digit Digit DP answers questions like "how many numbers up to N contain no digit greater than 5" WITHOUT iterating every number individually (impossible for huge N). It builds the number ONE DIGIT AT A TIME, tracking whether the prefix built so far is still "tight" (equal to N's prefix, constraining future digit choices) or already "free" (strictly less, so any digit is allowed).
More lessons in Dynamic Programming
- Fibonacci (DP)
- Climbing Stairs
- House Robber
- Kadane (DP)
- Grid Paths
- Unique Paths
- Minimum Path Sum
- 0/1 Knapsack
- Unbounded Knapsack
- Bounded Knapsack
- Subset Sum
- Equal Partition
- Target Sum
- Longest Common Subsequence - LCS
- Longest Common Substring
- Edit Distance
- Longest Palindromic Subsequence
- Palindrome Partitioning
- Longest Increasing Subsequence - LIS
- Number of LIS
- Maximum Sum Increasing Subsequence
- Matrix Chain Multiplication
- Burst Balloons
- Optimal BST
- Diameter (Tree DP)
- Maximum Path Sum (Tree DP)
- Tree Independent Set
- Traveling Salesman Problem
- Assignment Problems
- Digit Constraints