对字符串的dp还是挺难想出来的，其实情况往往都是自己想复杂了。哎 说说这一道题，dp【i】【j】 分别代表i是t，子串 。 j是原串 如果t i ！= s j，Dp【i】【j】 = dp【i】【j -1】，因为既然不匹配，那么原串多一个字符也不影响，所以就等于上一个j-1
如果相等，就是匹配的话，分两个情况 1，t i 和s j匹配，那么dp【i】【j】 就加上dp【i - 1】【j - 1】 2，虽然t i 和s j匹配，但是我们不把他们匹配的话，就是说加入t i已经跟之前s 0 到 s j-1 匹配了，就是多一个sj字符而已，所以dp【i】【j】 就加上dp【i】【j - 1】
2刷的时候要重新想， 而且要刷那个只用一维vector的那个dp。
class Solution {public: int numDistinct(string s, string t) { int n = s.length(); int m = t.length(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for(int j = 0; j <= n; ++ j) dp[0][j] = 1; for(int j = 1; j <= n; ++ j) for(int i = 1; i <= m; ++ i) dp[i][j] = t[i - 1] == s[j - 1] ? dp[i - 1][j - 1] + dp[i][j - 1] : dp[i][j - 1]; return dp[m][n]; }};新闻热点
疑难解答
