Examples: LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3. LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4. #include<bits/stdc++.h> int max(int a, int b); int lcs( char *X, char *Y, int m, int n ) { int L[m+1][n+1]; int i, j; for (i=0; i<=m; i++) { for (j=0; j<=n; j++) { if (i == 0 || j == 0) L[i][j] = 0; else if (X[i-1] == Y[j-1]) L[i][j] = L[i-1][j-1] + 1; else L[i][j] = max(L[i-1][j], L[i][j-1]); } } //L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] return L[m][n]; } // Utility function to get max of 2 integers int max(int a, in...
Posts
Showing posts with the label paytm
No of paths from top left to bottom right in a Matrix Linked to the concept of Longest Common Subsequence
- Get link
- X
- Other Apps
Count all possible paths from top left to bottom right The task is to count all the possible paths from top left to bottom right of a mXn matrix with the constraints that from each cell you can either move only to right or down. Input: First line consists of T test cases. First line of every test case consists of N and M, denoting the number of rows and number of column respectively. Output: Single line output i.e count of all the possible paths from top left to bottom right of a mXn matrix. Since output can be very large number use %10^9+7. Constraints: 1<=T<=100 1<=N<=100 1<=M<=100 Example: Input: 1 3 3 Output: 6 #include <iostream> using namespace std; int path(int m , int n) { int a[m][n]; // now we want to find the total paths from left top to bottom right //we use the concept of longest common subsequence to do it //in l.c.s we check if a[i]==a[j] // if true then done add 1 to diagnol eleme...