115.不同的子序列

链接：115.不同的子序列
难度：Hard
标签：字符串、动态规划
简介：给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

题解 1 - typescript

• 编辑时间：2021-03-17
• 执行用时：100ms
• 内存消耗：41.6MB
• 编程语言：typescript
• 解法介绍：[参考链接](https://leetcode-cn.com/problems/distinct-subsequences/solution/bu-tong-de-zi-xu-lie-by-leetcode-solutio-urw3/)。

function generateMatrix(n: number): number[][] {
        const ans: number[][] = new Array(n).fill(0).map(_ => new Array(n));
        let num = 1;
        dfs(0, n - 1);
        retfunction numDistinct(s: string, t: string): number {
          const sLen = s.length;
          const tLen = t.length;
          if (sLen < tLen) return 0;
          const dp = new Array(sLen + 1).fill(0).map(_ => new Array(tLen + 1).fill(0));
          for (let i = 0; i <= sLen; i++) dp[i][tLen] = 1;
          for (let i = sLen - 1; i >= 0; i--) {
            for (let j = tLen - 1; j >= 0; j--) {
              if (s[i] === t[j]) {
                dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
              } else {
                dp[i][j] = dp[i + 1][j];
              }
            }
          }
          return dp[0][0];
        }