René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"115.不同的子序列","articleBody":"[原题地址](https://leetcode-cn.com/problems/distinct-subsequences/)\r\n\r\n\u003e 给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。\r\n\u003e 一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余\u003e 字符相对位置所组成的新字符串。（例如，\"ACE\" 是 \"ABCDE\" 的一个子序列，而\u003e \"AEC\" 不是）\r\n\r\n### 题解\r\n子序列 T 在 S 中出现的次数 = T - 1 在 S 中的次数 + T - 1 在 S - 1 中出现的次数（前提是 S[-1] === T[-1]）\r\n\r\n写成动态规划方程\r\n\r\n![](http://latex.codecogs.com/gif.latex?f(T,%20S)%20=%20%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%20f(T,%20S-1),%20T%5B-1%5D%20!==%20S%5B-1%5D%20\u0026%20%5C%5C%20f(T,%20S-1)+f(T-1,%20S-1),%20T%5B-1%5D%20===%20S%5B-1%5D%20\u0026%20%5C%5C%20%5Cend%7Bmatrix%7D%5Cright.)\r\n\r\n### 代码\r\n```js\r\n/**\r\n * @param {string} s\r\n * @param {string} t\r\n * @return {number}\r\n */\r\nvar numDistinct = function(s, t) {\r\n  let res = new Array()\r\n  for (let i = 0; i \u003c= t.length; i++) {\r\n    let tem = new Array(s.length + 1).fill(0)\r\n    res.push(tem.slice())\r\n  }\r\n\r\n  for(let i = 0; i \u003c= s.length; i++) {\r\n    res[0][i] = 1\r\n  }\r\n\r\n  for (let i = 1; i \u003c= t.length; i++) {\r\n    for (let j = 1; j \u003c= s.length; j++) {\r\n      res[i][j] += res[i][j-1]\r\n      if (t[i-1] === s[j-1]) {\r\n        res[i][j] += res[i-1][j-1]\r\n      }\r\n    }\r\n  }\r\n  return res[t.length][s.length]\r\n};\r\n```","author":{"url":"https://github.com/feikerwu","@type":"Person","name":"feikerwu"},"datePublished":"2020-02-28T07:02:44.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":0},"url":"https://github.com/4/algorithm-camp/issues/4"}