干货｜leetcode部分动态规划记录贴

vlambda
2020-05-12

干货｜leetcode部分动态规划记录贴

leetcode部分动态规划记录贴

如果p[j+1] 不是通配符 ‘’ ，则f[i] [j]是真，当且仅当s[i]可以和p[j]匹配，且f[i+1] [j+1]是真；如果p[j+1]是通配符 '’，则下面的情况只要有一种满足，f[i] [j]就是真；f[i] [j+2]是真；s[i]可以和p[j]匹配，且f[i+1] [j]是真;

class Solution {public: vector<vector<int>> dp; int lens, lenp; bool isMatch(string s, string p) { lens = s.size(); lenp = p.size(); dp = vector<vector<int>>(lens + 1, vector<int>(lenp + 1, -1)); return sol(s, p, 0, 0); } bool sol(string &s, string &p, int x, int y) { if(dp[x][y] != -1) return dp[x][y]; if(y == lenp) return dp[x][y] = x == lens; bool match = (s[x] == p[y] || p[y] == '.') && x < lens;// 越界 bool tmp; if(p[y + 1] == '*' && y + 1 < lenp) { tmp = ( (match && sol(s, p, x + 1, y) ) || sol(s, p, x, y + 2));// 多匹配||0匹配 } else { tmp = match && sol(s, p, x + 1, y + 1); } return tmp; }};

编辑距离

状态表示：f[i,j] 表示将 word1 的前 i 个字符变成 word2 的前 j 个字符，最少需要进行多少次操作。状态转移，一共有四种情况：

将 word1[i]删除或在 word2[j]后面添加 word1[i]，则其操作次数等于 f[i−1,j]+1;
将 word2[j]删除或在 word1[i]后面添加 word2[j]，则其操作次数等于 f[i,j−1]+1;
如果 word1[i]=word2[j]，则其操作次数等于 f[i−1,j−1];
如果 word1[i]≠word2[j]，则其操作次数等于 f[i−1,j−1]+1；
时间复杂度分析：状态数 O(n2)，状态转移复杂度是 O(1)，所以总时间复杂度是 O(n2);

class Solution {public: vector<vector<int>> dp; int len1, len2; int minDistance(string word1, string word2) { len1 = word1.size(), len2 = word2.size(); dp = vector<vector<int>>(len1 + 1, vector<int>(len2 + 1)); for(int i = 0; i <= len1; i ++) dp[i][0] = i; for(int i = 0; i <= len2; i ++) dp[0][i] = i; for(int i = 1; i <= len1; i ++) { for(int j = 1; j <= len2; j ++) { if(word1[i - 1] != word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = dp[i - 1][j - 1]; } dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j]); dp[i][j] = min(dp[i][j - 1] + 1, dp[i][j]); } } return dp[len1][len2]; }};