Distinct Subsequences
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.dynamic_programming;
import java.util.*;
/ * Problem: Distinct Subsequences * Group: 11. Dynamic Programming */ / * ============================================================================================ * PROBLEM: Distinct Subsequences * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given two strings S and T. Count the number of distinct subsequences of S which equals T. * * --------------------- * 2. Logical Breakdown * --------------------- * Let dp[i][j] be the number of ways T[0..j-1] can be formed using S[0..i-1]. * * Recurrence: * 1. If S[i-1] != T[j-1]: * We cannot use S[i-1] to match T[j-1]. We must rely on previous chars of S. * dp[i][j] = dp[i-1][j] * * 2. If S[i-1] == T[j-1]: * We have two choices: * a) Use S[i-1] to match T[j-1]: We need to find T[0..j-2] in S[0..i-2]. * -> dp[i-1][j-1] * b) Ignore S[i-1] (Maybe there's another occurrence later in S that matches T[j-1]): * -> dp[i-1][j] * dp[i][j] = dp[i-1][j-1] + dp[i-1][j] * * Base Case: * dp[i][0] = 1 (Empty T is a subsequence of any S exactly once). * * ============================================================================================ */ public class DistinctSubsequences { public int solve(int A) { // TODO: Implement solution return 0; }
public int numDistinct(String rabbbit, String rabbit) {
return 1;
}
}