【代码随想录】【算法训练营】【第51天】 [115]不同的子序列 [583]两个字符串的删除操作 [72]编辑距离

前言

思路及算法思维，指路代码随想录。
题目来自 LeetCode。

day 51，周四，又是不能坚持的一天~

题目详情

[115] 不同的子序列

题目描述

115 不同的子序列

解题思路

前提：转换为t为s的子序列的个数，元素的相对顺序一致
思路：动态规划动态规划 dp[i][j]: 字符串s以i - 1为结尾的[0, i - 1] 中出现字符串t以j - 1为结尾的[0, j - 1]中的个数，s[i-1] == t[j-1]时, dp[i][j] = dp[i-1][j-1] + dp[i-1][j]；s[i-1] != t[j-1]时, dp[i][j] = dp[i-1][j]
重点：递推公式的推导、dp数组初始化

代码实现

C语言

动态规划

用例超出int， long long int数值范围，使用unsigned long long类型

// 动态规划 dp[i][j]: 字符串s以i - 1为结尾的[0, i - 1] 中出现 字符串t以j - 1为结尾的[0, j - 1]中的个数
// s[i-1] == t[j-1]时, dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
// s[i-1] != t[j-1]时, dp[i][j] = dp[i-1][j]

int numDistinct(char* s, char* t) {
    int sLen = strlen(s);
    int tLen = strlen(t);
    unsigned long long dp[sLen + 1][tLen + 1];
    // dp初始化
    for (int m = 0; m <= sLen; m++) {
        dp[m][0] = 1;
    }
    for (int n = 1; n <= tLen; n++) {
        dp[0][n] = 0;
    }
    // 循环
    for (int i = 1; i <= sLen; i++) {
        for (int j =1; j <= tLen; j++) {
            if (s[i - 1] == t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[sLen][tLen];
}

[583] 两个字符串的删除操作

题目描述

583 两个字符串的删除操作

解题思路

前提：转化为删除word1中与word2的公共子序列(元素相对位置不变)之外的字符的问题 (两个单词均可以删除)
思路：动态规划 dp[i][j]: 以i-1下标为结尾的单词word1和以j-1下标为结尾的单词word2,使其相同所需的最小步数(删除次数)，word1[i-1] == word2[j-1]时, dp[i][j] = dp[i-1][j-1]；word1[j-1] != word2[j-1]时, 分为3种情况, dp[i][j] = min(dp[i-1][j-1]+2, dp[i-1][j]+1, dp[i][j-1]+1)，因为dp[i][j-1] = dp[i-1][j-1]+1,所以可简化为 dp[i][j] = min(dp[i][j-1]+1, dp[i-1][j]+1)
重点：递推公式的推导、dp数组初始化

代码实现

C语言

动态规划

// 转化为 删除word1中与word2的公共子序列(元素相对位置不变)之外的字符 的问题 (两个单词均可以删除)
// 动态规划 dp[i][j]: 以i-1下标为结尾的单词word1和以j-1下标为结尾的单词word2,使其相同所需的最小步数(删除次数)
// word1[i-1] == word2[j-1]时, dp[i][j] = dp[i-1][j-1]
// word1[j-1] != word2[j-1]时, 分为3种情况, dp[i][j] = min(dp[i-1][j-1]+2, dp[i-1][j]+1, dp[i][j-1]+1)
// 因为dp[i][j-1] = dp[i-1][j-1]+1,所以可简化为 dp[i][j] = min(dp[i][j-1]+1, dp[i-1][j]+1)

int minFun(int p1, int p2)
{
    return p1 < p2 ? p1 : p2;
}

int minDistance(char* word1, char* word2) {
    int word1_len = strlen(word1);
    int word2_len = strlen(word2);
    int dp[word1_len + 1][word2_len + 1];
    // dp初始化
    for (int m = 0; m <= word1_len; m++) {
        dp[m][0] = m;
    }
    for (int n = 1; n <= word2_len; n++) {
        dp[0][n] = n;
    }
    // 遍历
    for (int i = 1; i <= word1_len; i++) {
        for (int j = 1; j <= word2_len; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = minFun(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
            }
        }
    }
    return dp[word1_len][word2_len];
}

[72] 编辑距离

题目描述

72 编辑距离

解题思路

前提：通过增删改的操作，使得两个单词相同 (两个单词均可修改)
思路：动态规划 dp[i][j]: 以i-1下标为结尾的单词word1和以j-1下标为结尾的单词word2,使其相同所需的最小操作数(增删改)， word1[i-1] == word2[j-1]时, dp[i][j] = dp[i-1][j-1]， word1[j-1] != word2[j-1]时, 分为3种情况[增加word1(相当于删除word2)/删除/word1/修改word1]，dp[i][j] = min(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+1)
重点：递推公式的推导、dp数组初始化

代码实现

C语言

动态规划

// 动态规划 dp[i][j]: 以i-1下标为结尾的单词word1和以j-1下标为结尾的单词word2,使其相同所需的最小操作数(增删改)
// word1[i-1] == word2[j-1]时, dp[i][j] = dp[i-1][j-1]
// word1[j-1] != word2[j-1]时, 分为3种情况[增加word1(相当于删除word2)/删除/word1/修改word1]
// dp[i][j] = min(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+1)

int minFun(int p1, int p2)
{
    return p1 < p2 ? p1 : p2;
}

int minDistance(char* word1, char* word2) {
    int word1_len = strlen(word1);
    int word2_len = strlen(word2);
    int dp[word1_len + 1][word2_len + 1];
    // dp初始化
    for (int m = 0; m <= word1_len; m++) {
        dp[m][0] = m;
    }
    for (int n = 1; n <= word2_len; n++) {
        dp[0][n] = n;
    }
    // 遍历
    for (int i = 1; i <= word1_len; i++) {
        for (int j = 1; j <= word2_len; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = minFun(dp[i - 1][j - 1] + 1, minFun(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
            }
        }
    }
    return dp[word1_len][word2_len];
}