對字符串的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]; }};新聞熱點
疑難解答
