115. 不同的子序列
回溯法，会超时
注意下面代码中的nonlocal声明，在嵌套函数中，想要给一个变量声明为非局部变量（当函数修改上一级函数定义的变量时），需要这个声明，此时用global不行。nonlocal时python3独有的。
global与nonlocal的区别
第一，两者的功能不同。global关键字修饰变量后标识该变量是全局变量，对该变量进行修改就是修改全局变量，而nonlocal关键字修饰变量后标识该变量是上一级函数中的局部变量，如果上一级函数中不存在该局部变量，nonlocal位置会发生错误（最上层的函数使用nonlocal修饰变量必定会报错）。
第二，两者使用的范围不同。global关键字可以用在任何地方，包括最上层函数中和嵌套函数中，即使之前未定义该变量，global修饰后也可以直接使用，而nonlocal关键字只能用于嵌套函数中，并且外层函数中定义了相应的局部变量，否则会发生错误。
class Solution:
def numDistinct(self, s: str, t: str) -> int:
tlen = len(t)
slen = len(s)
ans = 0
def dg(start,p):
if p==tlen:
nonlocal ans
ans += 1
elif start<slen and slen-start>=tlen-p:
for i in range(start,slen):
if s[i]==t[p]:
dg(i+1,p+1)
dg(0,0)
return ans
动态规划：
dp[i][j]表示有几种可以从s[:i+1]得到t[:j+1]的方案。
当s[i]==t[j]时：dp[i][j] = dp[i - 1][j] + dp[i-1][j-1]
当s[i]!=t[j]时：dp[i][j] = dp[i - 1][j]
看下代码里面dp矩阵第一行第一列的值怎么确定的。
class Solution:
def numDistinct(self, s: str, t: str) -> int:
tlen = len(t)
slen = len(s)
if tlen==0 or slen==0:
return 0
dp = [ [0]*tlen for _ in range(slen)]
# 先确定 dp[0][0] 的值
if s[0]==t[0]:
dp[0][0] = 1
# dp[0][1] 到 dp[0][-1]全部是0，不需要初始化
# 下面确定 dp[1][0] 到 dp[-1][0] 的值
for i in range(1,slen):
if t[0]==s[i]:
dp[i][0] = 1+dp[i-1][0]
else:
dp[i][0] = dp[i - 1][0]
for i in range(1,slen):
for j in range(1,tlen):
if s[i]==t[j]:
dp[i][j] = dp[i - 1][j] + dp[i-1][j-1]
else:
dp[i][j] = dp[i - 1][j]
return dp[-1][-1]
关键词：动态规划
