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]

关键词：动态规划