C語言字符串中的動態規劃應用

在C語言中，字符串是一個非常重要的數據類型，而動態規劃是一種解決復雜問題的方法。在處理字符串時，動態規劃可以幫助我們找到最優解，例如在編輯距離、最長公共子序列等問題中。

下面是一個使用動態規劃解決字符串相關問題的例子：編輯距離（Levenshtein距離）。

編輯距離是指將一個字符串轉換為另一個字符串所需的最少操作次數。允許的操作包括插入、刪除和替換一個字符。我們可以使用動態規劃來計算兩個字符串之間的編輯距離。

#include<stdio.h>
#include<string.h>
#include <stdlib.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int edit_distance(const char *str1, const char *str2) {
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int **dp = (int **)malloc((len1 + 1) * sizeof(int *));
    for (int i = 0; i <= len1; i++) {
        dp[i] = (int *)malloc((len2 + 1) * sizeof(int));
    }

    for (int i = 0; i <= len1; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= len2; j++) {
        dp[0][j] = j;
    }

    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            }
        }
    }

    int result = dp[len1][len2];
    for (int i = 0; i <= len1; i++) {
        free(dp[i]);
    }
    free(dp);
    return result;
}

int main() {
    const char *str1 = "kitten";
    const char *str2 = "sitting";
    printf("編輯距離: %d\n", edit_distance(str1, str2));
    return 0;
}

這個程序首先計算兩個字符串的長度，然后創建一個動態規劃表格，用于存儲子問題的解。接下來，我們初始化表格的第一行和第一列，表示將一個空字符串轉換為另一個字符串所需的操作次數。然后，我們遍歷兩個字符串，比較它們的每個字符，根據動態規劃的狀態轉移方程更新表格。最后，我們返回表格右下角的值，即兩個字符串之間的編輯距離。

這個例子展示了如何在C語言中使用動態規劃解決字符串相關問題。當然，還有很多其他字符串問題可以使用動態規劃來解決，例如最長公共子序列、最長公共子串等。