I have written a program to find LCS (Longest Common Subsequences) using Dynamic Programming with DP array. Coursera said it is not fast enough. Is there some sort of ways to improve it?
I have tried my best to simplify it as much as possible already. Any advice is welcome.
a & b are two different arrays of number sequence.
i & j are indexes for a & b.
n & m show how many numbers in each sequence.
dp[][] is an array for memoization.
#include <stdio.h>
#include <stdlib.h>
int lcs2(int a[], int b[], int i, int j, int n, int m, int dp[n+1][m+1]) {
int counter = 0;
while(i < n && j < m){
if (dp[i][j] != 0) //1.0 return stored ans if exist
return dp[i][j];
//2.0 no stored result, run below
else if (a[i] == b[j]){ //2.1 check if both digits are the same
counter++; //2.1.1 update counter
i++; //2.1.2 both i & j move forward
j++;
}
else { //2.2 both int are not the same
//2.2.1 check the next best move
int ans1 = lcs2(a, b, i+1, j, n, m, dp); //when i+1
int ans2 = lcs2(a, b, i, j+1, n, m, dp); //when j+1
if (ans1 >= ans2){ //2.2.2 compare and move
i++;
}
else { //2.2.2
j++;
}
}//else ends
}
dp[i][j] = counter;
return counter;
}
int main() {
int n;
scanf("%d", &n);
int a[n];
for (int i = 0; i < n; i++) {
scanf(" %d", &a[i]);
}
int m;
scanf("%d", &m);
int b[m];
for (int i = 0; i < m; i++) {
scanf(" %d", &b[i]);
}
int dp[n+1][m+1]; //length +1
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
dp[i][j] = 0;
}
}
printf("%d
", lcs2(a, b, 0, 0, n, m, dp));
return 0;
}
question from:
https://stackoverflow.com/questions/65847263/better-runtime-c-lcs-longest-common-subsequence-of-two-sequences 与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…