LeetCode.1143.583.72.322.343(动态规划)

1143.最长公共子序列

class Solution {
 public:
  int longestCommonSubsequence(string text1, string text2) {
    int text1S = text1.size();
    int text2S = text2.size();
    vector<vector<int>> dp(text1S + 1, vector(text2S + 1, 0));
    for (int i = text1S - 1; i >= 0; i--) {
      for (int j = text2S - 1; j >= 0; j--) {
        if (text1[i] == text2[j]) {
          dp[i][j] = dp[i + 1][j + 1] + 1;
        }
        dp[i][j] = max(dp[i + 1][j], dp[i][j]);
        dp[i][j] = max(dp[i][j + 1], dp[i][j]);
      }
    }
    return dp[0][0];
    // 44/44 cases passed (40 ms)
    // Your runtime beats 5.66 % of cpp submissions
    // Your memory usage beats 44.76 % of cpp submissions (12.8 MB)
  }
};

583.两个字符串的删除操作

class Solution {
 public:
  int minDistance(string word1, string word2) {
    vector<vector<int>> dp(word1.size(), vector<int>(word2.size(), 0));
    dp[0][0] = word1[0] == word2[0] ? 0 : 2;
    bool flag = (dp[0][0] == 2);
    for (int i = 1; i < word1.size(); i++) {
      if (word1[i] == word2[0] && flag) {
        dp[i][0] = dp[i - 1][0] - 1;
        flag = !flag;
      } else {
        dp[i][0] = dp[i - 1][0] + 1;
      }
    }
    flag = (dp[0][0] == 2);
    for (int i = 1; i < word2.size(); i++) {
      if (word2[i] == word1[0] && flag) {
        dp[0][i] = dp[0][i - 1] - 1;
        flag = !flag;
      } else {
        dp[0][i] = dp[0][i - 1] + 1;
      }
    }
    for (int i = 1; i < word1.size(); i++) {
      for (int j = 1; j < word2.size(); j++) {
        if (word1[i] == word2[j]) {
          dp[i][j] = dp[i - 1][j - 1];
        } else {
          dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
        }
      }
    }
    return dp.back().back();
    // 1306/1306 cases passed (4 ms)
    // Your runtime beats 99.97 % of cpp submissions
    // Your memory usage beats 86.73 % of cpp submissions (11.8 MB)
  }
};

72.编辑距离

class Solution {
 public:
  int minDistance(string word1, string word2) {
    if (word1 == "") return word2.size();
    if (word2 == "") return word1.size();
    vector<vector<int>> dp(word1.size(), vector<int>(word2.size(), 0));
    dp[0][0] = word1[0] == word2[0] ? 0 : 1;
    bool judge = (dp[0][0] == 1);
    for (int i = 1; i < dp.size(); i++) {
      if (judge && word1[i] == word2[0]) {
        judge = 0;
        dp[i][0] = dp[i - 1][0];
      } else
        dp[i][0] = dp[i - 1][0] + 1;
    }
    judge = (dp[0][0] == 1);
    for (int i = 1; i < dp[0].size(); i++) {
      if (judge && word2[i] == word1[0]) {
        judge = 0;
        dp[0][i] = dp[0][i - 1];
      } else
        dp[0][i] = dp[0][i - 1] + 1;
    }
    for (int i = 1; i < dp.size(); i++) {
      for (int j = 1; j < dp[0].size(); j++) {
        if (word1[i] == word2[j]) {
          dp[i][j] = dp[i - 1][j - 1];
        } else {
          dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
        }
      }
    }
    for (int i = 0; i < dp.size(); i++) {
      for (int j = 0; j < dp[0].size(); j++) {
        cout << dp[i][j] << " ";
      }
      cout << endl;
    }
    return dp.back().back();
    // 1146/1146 cases passed (112 ms)
    // Your runtime beats 6.51 % of cpp submissions
    // Your memory usage beats 73.95 % of cpp submissions (8.6 MB)
  }
};

322.零钱兑换

class Solution {
 public:
  int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX - 1);
    dp[0] = 0;
    for (int i = 0; i < coins.size(); i++) {
      for (int j = coins[i]; j <= amount; j++) {
        dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
      }
    }
    return dp.back() == INT_MAX - 1 ? -1 : dp.back();
    // 188/188 cases passed (68 ms)
    // Your runtime beats 74.34 % of cpp submissions
    // Your memory usage beats 70.83 % of cpp submissions (14 MB)
    //*背包问题
  }
};

343.整数拆分

class Solution {
 public:
  int integerBreak(int n) {
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
    for (int i = 2; i <= n; i++) {
      for (int j = n; j >= 2; j--) {
        if (j == i) {
          dp[i][j] = 1;
        } else if (j == 2) {
          dp[i][j] = (i / 2) * (i - i / 2);
        } else {
          if (j > 2) {
            dp[i][j] = dp[i - 1][j] + dp[i - 1 - (int)((i - 1) / j)][j - 1];
          }
        }
      }
    }
    int ans = 0;
    for (int i = 2; i <= n; i++) {
      ans = max(ans, dp[n][i]);
    }
    return ans;
    // 50/50 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 5.59 % of cpp submissions (6.7 MB)
    /*
    *思路如下：
    i=x1+x2+x3+...+xj
    dp[i][j]=x1*x2*...*xj
    dp[i+1][j]=(xmin+1)*xothers=dp[i][j]+xothers=dp[i][j]+dp[i-xmin][j-1]
    *完全由自己想出来的！哼哼*/
  }
};