所以以下是我为算法编写的代码。我找不到它有什么问题。测试用例应该分别产生 12、4 和 3,而是分别产生 8、1 和 2。我误解了算法结构吗?
#include <stdio.h>
#define MAX_STRING_LENGTH 100
void clear_memo(int memo[][MAX_STRING_LENGTH]);
// Returns the larger of a and b
int max(int a, int b){
return a ? a > b : b;
}
int lcs_length(char A[], char B[], int i, int j, int memo[][MAX_STRING_LENGTH]){
if(i == 0 && j == 0){
clear_memo(memo);
}
if (memo[i][j] > 0){
return memo[i][j];
}
if (A[i] == '\0' || B[j] == '\0'){
memo[i][j] = 0;
}
else if(A[i] == B[j]){
memo[i][j] = 1 + lcs_length(A, B, i+1, j+1, memo);
}
else{
memo[i][j] = max(lcs_length(A, B, i+1, j, memo), lcs_length(A, B, i, j+1, memo));
}
return memo[i][j];
}
// Makes all the entries zero in the memo array
void clear_memo(int memo[][MAX_STRING_LENGTH]){
for(int i = 0; i < MAX_STRING_LENGTH; i++){
for(int j = 0; j < MAX_STRING_LENGTH; j++){
memo[i][j] = 0;
}
}
}
// Tests the lcs_length() function
int main(){
int memo[MAX_STRING_LENGTH][MAX_STRING_LENGTH];
char a[] = "yo dawg how you doing?";
char b[] = "yo dawg zhzzzozw?";
printf("%d\n", lcs_length(a,b,0,0,memo));
char c[] = "nano";
char d[] = "nematode knowledge";
printf("%d\n", lcs_length(c,d,0,0,memo));
char e[] = "abcd";
char f[] = "abdc";
printf("%d\n", lcs_length(e,f,0,0,memo));
return 0;
}