在C語言中,動態規劃可以有效地解決回文相關問題,比如求解最長回文子串或者判斷一個字符串是否是回文串等問題。以下是一個簡單的示例,展示了如何使用動態規劃來判斷一個字符串是否是回文串:
#include <stdio.h>
#include <string.h>
int isPalindrome(char *str) {
int n = strlen(str);
int dp[n][n];
// 初始化動態規劃數組
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
// 計算動態規劃數組
for (int len = 2; len <= n; len++) {
for (int i = 0; i < n - len + 1; i++) {
int j = i + len - 1;
if (len == 2 && str[i] == str[j]) {
dp[i][j] = 1;
} else if (str[i] == str[j] && dp[i + 1][j - 1] == 1) {
dp[i][j] = 1;
} else {
dp[i][j] = 0;
}
}
}
return dp[0][n - 1];
}
int main() {
char str[] = "abba";
if (isPalindrome(str)) {
printf("The string is a palindrome.\n");
} else {
printf("The string is not a palindrome.\n");
}
return 0;
}
在這個示例中,我們定義了一個函數isPalindrome
來判斷一個字符串是否是回文串。我們使用一個二維動態規劃數組dp
來存儲已經計算過的子串是否是回文串的結果。通過填充和更新動態規劃數組,最終可以判斷整個字符串是否是回文串。通過這種動態規劃的方法,我們可以高效地解決回文相關問題。