给定字符串s和t,计算s中有多少不同子序列可以构成t,子序列通过删除一些元素实现。
动态规划实现,递推关系为faster than 60%
/**
* @param {string} s
* @param {string} t
* @return {number}
*/
var numDistinct = function(s, t) {
var m = s.length
var n = t.length
var dp = Array(m + 1).fill().map(item => Array(n + 1).fill(0))
for(var i = 0; i <= m; i++){
dp[i][0] = 1
}
for(var i = 0; i < m; i++){
for(var j = 0; j < n; j++){
if(s[i] === t[j])
dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1]
else
dp[i + 1][j + 1] = dp[i][j + 1]
}
}
return dp[m][n]
};