The shortest common supersequence (SCS) is the problem of finding the shortest supersequence Z of given sequences X and Y such that both X & Y are subsequences of Z.
The longest repeated subsequence (LRS) problem is the problem of finding the longest subsequences of a string that occurs at least twice.
The Longest Palindromic Subsequence (LPS) problem is the problem of finding the longest subsequences of a string that is also a palindrome.
The longest common substring problem is the problem of finding the longest string (or strings) that is a substring (or are substrings) of two strings.
Given two sequences, print all the possible longest common subsequences present in them.
Write space optimized version of LCS problem.
The longest common subsequence (LCS) problem is the problem of finding the longest subsequence that is present in given two sequences in the same order. i.e. find a longest sequence which can be obtained from the first original sequence by deleting some items, and from the second original sequence by deleting other items.
Dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions using a memory-based data structure (array, map,etc). Each of the subproblem solutions is indexed in some way, typically based on the values of …
Given an M x M matrix, find maximum sum sub-matrix present in it.
Given a M x N matrix, calculate maximum sum submatrix of size k x k in a given M x N matrix in O(M*N) time. Here, 0 < k < M, N.
Given a M x N matrix and two coordinates (p, q) and (r, s) which represents top-left and bottom-right coordinates of a sub-matrix of the given matrix, calculate the sum of all elements present in the sub-matrix in O(1) time. Here, 0 < = p < r < M and 0
Given an island in the form of square matrix and a point inside the matrix where a person is standing. The person is allowed to move one step in any direction (right, left, top, down) on the matrix. If he steps outside the matrix, he dies. Calculate the probability that he is alive after he …