Better runtime? - C - LCS - Longest Common SubSequence of two sequences

Question

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

Answer 1

Waitting for answers