對(duì)字符串的dp還是挺難想出來(lái)的，其實(shí)情況往往都是自己想復(fù)雜了。哎 說(shuō)說(shuō)這一道題，dp【i】【j】 分別代表i是t，子串 。 j是原串 如果t i ！= s j，Dp【i】【j】 = dp【i】【j -1】，因?yàn)榧热徊黄ヅ?，那么原串多一個(gè)字符也不影響，所以就等于上一個(gè)j-1
如果相等，就是匹配的話，分兩個(gè)情況 1，t i 和s j匹配，那么dp【i】【j】 就加上dp【i - 1】【j - 1】 2，雖然t i 和s j匹配，但是我們不把他們匹配的話，就是說(shuō)加入t i已經(jīng)跟之前s 0 到 s j-1 匹配了，就是多一個(gè)sj字符而已，所以dp【i】【j】 就加上dp【i】【j - 1】
2刷的時(shí)候要重新想， 而且要刷那個(gè)只用一維vector的那個(gè)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]; }};新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
