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 Dynamic Programming
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...
Find Binomial Coefficient
- Get link
- X
- Other Apps
// A Dynamic Programming based solution that uses // table C[][] to calculate the Binomial Coefficient #include<bits/stdc++.h> using namespace std; // Prototype of a utility function that // returns minimum of two integers int min(int a, int b); // Returns value of Binomial Coefficient C(n, k) int binomialCoeff(int n, int k) { int C[n + 1][k + 1]; int i, j; // Caculate value of Binomial Coefficient // in bottom up manner for (i = 0; i <= n; i++) { for (j = 0; j <= min(i, k); j++) { // Base Cases if (j == 0 || j == i) C[i][j] = 1; // Calculate value using previously ...
- Get link
- X
- Other Apps
// sieve of Atkin is a popular way to find all the prime numbers in range using the dp approach and is //better than the erronthesis approach // C++ program for implementation of Sieve of Atkin #include <bits/stdc++.h> using namespace std; int SieveOfAtkin(int limit) { // 2 and 3 are known to be prime if (limit > 2) cout << 2 << " "; if (limit > 3) cout << 3 << " "; // Initialise the sieve array with false values bool sieve[limit]; for (int i = 0; i < limit; i++) sieve[i] = false; for (int x = 1; x * x < limit; x++) { for (int y = 1; y * y < limit; y++) { // Main part of Sieve of Atkin ...
Composites and Primes Sieve of Eratosthenes dp
- Get link
- X
- Other Apps
/* Given two integers L and R find the difference of number of composites and primes between the range L and R (both inclusive). Input: First line of input contains of an integer 'T' denoting number of test cases . Then T test cases follow. Each test contains two integers L and R . Output: For each case print an integer corresponding to the answer . Constraints: 1<=T<=100 1<=L<=R<=10^7 Example: Input: 2 4 4 4 6 Output: 1 1 */ // given l , r print no of comp- no of prime T.C->0.21 // normal approac i*i<=n gives TLE > 3.14 #include<bits/stdc++.h> using namespace std; bool prime[100001]; void SieveOfEratosthenes() { memset(prime, true, sizeof(prime)); prime[0]=false; prime[1]=false; for (int p=2; p*p<=10000000; p++) { if (prime[p] == true) // we make all multiples of prime false ...