Number of LIS
Learn Number of LIS (Dynamic Programming, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Counting HOW MANY Longest Increasing Subsequences Exist Track TWO arrays alongside each other: length[i] = LIS length ending at i (as before), and count[i] = how many distinct LIS of that length end at i. When extending from j to i, if the new length TIES the current best at i, ADD j's count; if it BEATS it, RESET to j's count.
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
- 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
- Counting Numbers (Digit DP)
- Digit Constraints