当前位置：首页 > article >正文

代码随想录算法训练营第四十五天|Day45 动态规划

article 2024/11/13 22:44:04

115.不同的子序列

https://programmercarl.com/0115.%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97.html

思路

#define MOD 1000000007
int numDistinct(char* s, char* t) {
    int m = strlen(s);
    int n = strlen(t);
    int dp[m + 1][n + 1];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1; 
    for (int i = 0; i <= m; i++) {
        dp[i][0] = 1; 
    }
    for (int j = 1; j <= n; j++) {
        dp[0][j] = 0; 
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i - 1] == t[j - 1]) {
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD;
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[m][n];
}

学习反思

动态规划解决了一个字符串问题。函数numDistinct计算字符串t在字符串s中出现的次数。代码中使用了一个二维数组dp来存储状态。dp[i][j]表示s的前i个字符中包含字符串t的前j个字符的子序列数。首先，初始化dp[0][0]为1表示空字符串是空字符串的子序列。然后，初始化dp[i][0]为1表示任意非空字符串是空字符串的子序列。初始化dp[0][j]为0表示任意字符串不能包含非空字符串。接下来，使用两层循环遍历数组s和数组t的每个字符。如果s[i-1]与t[j-1]相等，则有两种情况：一种是s的前i-1个字符中包含t的前j-1个字符的子序列数，另一种是s的前i-1个字符中包含t的前j个字符的子序列数。所以，dp[i][j]等于这两种情况的和。如果s[i-1]与t[j-1]不相等，则dp[i][j]等于s的前i-1个字符中包含t的前j个字符的子序列数。最后，返回dp[m][n]，即s包含t的子序列数。这段代码的时间复杂度是O(m*n)，其中m和n分别是字符串s和t的长度。

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

https://programmercarl.com/0583.%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C.html

思路

int minDistance(char* word1, char* word2) {
    int m = strlen(word1);
    int n = strlen(word2);
    int **dp = (int **)malloc((m + 1) * sizeof(int *));
    for (int i = 0; i <= m; i++) {
        dp[i] = (int *)malloc((n + 1) * sizeof(int));
    }
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i; 
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j; 
  }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]; 
            } else {
                dp[i][j] = (dp[i - 1][j] < dp[i][j - 1]) ? dp[i - 1][j] + 1 : dp[i][j - 1] + 1;
            }
        }
    }
    int result = dp[m][n];
    for (int i = 0; i <= m; i++) {
        free(dp[i]);
    }
    free(dp);
    return result;
}

学习反思

动态规划解决了一个字符串问题。函数minDistance计算将字符串word1转换成字符串word2所需的最小操作次数。代码中使用了一个二维数组dp来存储状态。dp[i][j]表示将word1的前i个字符转换成word2的前j个字符所需的最小操作次数。首先，动态申请二维数组dp的内存空间，并初始化数组。初始化dp[i][0]为i，表示将word1的前i个字符转换成空字符串所需的最小操作次数。初始化dp[0][j]为j，表示将空字符串转换成word2的前j个字符所需的最小操作次数。接下来，使用两层循环遍历字符串word1和字符串word2的每个字符。如果word1[i-1]与word2[j-1]相等，则不需要进行任何操作，所以dp[i][j]等于dp[i-1][j-1]。如果word1[i-1]与word2[j-1]不相等，则可以选择删除word1[i-1]或者插入word2[j-1]，取两种操作中的较小值，并加上一次操作的代价。最后，返回dp[m][n]，即将word1转换成word2所需的最小操作次数。由于申请了动态内存空间，需要在函数结束后释放内存，以避免内存泄漏。这段代码的时间复杂度是O(m*n)，其中m和n分别是字符串word1和word2的长度。

72. 编辑距离

https://programmercarl.com/0072.%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB.html

思路

int minDistance(char* word1, char* word2) {
    int m = strlen(word1);
    int n = strlen(word2);
    int **dp = (int **)malloc((m + 1) * sizeof(int *));
    for (int i = 0; i <= m; i++) {
        dp[i] = (int *)malloc((n + 1) * sizeof(int));
    }
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;
    }    
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j; 
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]; 
            } else {
                dp[i][j] = fmin(fmin(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
            }
        }
    }
    int result = dp[m][n];
    for (int i = 0; i <= m; i++) {
        free(dp[i]);
    }
    free(dp);
    return result;
}

学习反思

在计算dp[i][j]的时候，使用了fmin函数来取三者中的最小值，即dp[i - 1][j] + 1、dp[i][j - 1] + 1和dp[i - 1][j - 1] + 1中的最小值。这样可以简化代码并提高效率。其他部分保持不变，申请动态内存空间、初始化数组、更新dp[i][j]的值和释放内存空间的操作都没有改变。这段代码的时间复杂度仍然是O(m*n)。通过使用fmin函数，可以更清晰地表示出取三者中的最小值的操作。