Distinct Subsequences | LeetCode 115 | DP Explained

In this video, we solve Distinct Subsequences — LeetCode 115 using Dynamic Programming. We start with a recursive solution that explores the different ways to form `t` as a subsequence of `s`. We then optimize the overlapping subproblems using Memoization, convert the solution to Bottom-Up Tabulation, and finally reduce the space complexity using Space Optimization. What you'll learn Recursive approach Take / Not Take decision Why the recursive solution leads to TLE Memoization 2D Dynamic Programming Bottom-Up Tabulation Space optimization How to reduce DP space from O(m × n) to O(n) Problem LeetCode 115 — Distinct Subsequences Given two strings `s` and `t`, return the number of distinct subsequences of `s` which equals `t`. Pattern Dynamic Programming — 2D DP Complexity Recursion: O(2^m) Time, O(m) Stack Space Memoization: O(m × n) Time, O(m × n) Space Tabulation: O(m × n) Time, O(m × n) Space Space Optimized: O(m × n) Time, O(n) Space If you're learning DSA and preparing for coding interviews, follow along as we solve LeetCode problems and understand the patterns behind them. #LeetCode #DSA #DynamicProgramming #DP #CodingInterview