模版题-动态规划-不同的子序列( 遍历顺序的重要性 )
- 版权声明：本站原创文章，于2026-06-05，由 管理员 发表。
- 转载请注明： 模版题-动态规划-不同的子序列( 遍历顺序的重要性 ) | CodeGarden
```python
class Solution:
# 给你两个字符串s和t ，统计并返回在s的子序列中t出现的个数。
# 1 <= s.length, t.length <= 1000
# s 和 t 由英文字母组成
def numDistinct(self, s: str, t: str) -> int:
ns = len( s )
nt = len( t )
if nt > ns: return 0
# 暴力: 枚举s中每个元素的状态(保留;删除),所有排列序列和t对比,看出现次数。
# 典型dp优化: dp[ i ][ j ]表示以t[ i ]和s[ j ]结尾的字符串A和B,B的子序列出现A的个数
dp = [ [ 0 for _ in range( ns ) ] for _ in range( nt ) ]
# 初始化
# A=t[0] B=s[0]~s[ j ]
count = 0
for j in range( ns ):
if s[ j ] == t[ 0 ]:
count += 1
dp[ 0 ][ j ] = count
# 遍历顺序 !important
for i in range( 1, nt ):
for j in range( i, ns ):
if s[ j ] == t[ i ]:
# 相同时:
# + dp[ i - 1 ][ j - 1 ]: s[j] == t[i] 所以次数取决于t[i-1]和s[j-1]结尾的字符串
# + dp[ i ][ j - 1 ] why? 相同时,可以使用相同的作比较 同样可以使用不同的作比较
# 这才是相同时次数的所有情况 所以需要额外增加 dp[ i ][ j - 1 ]
dp[ i ][ j ] = dp[ i - 1 ][ j - 1 ] + dp[ i ][ j - 1 ]
else: dp[ i ][ j ] = dp[ i ][ j - 1 ]
return dp[ nt - 1 ][ ns - 1 ]
```