Shortest Common Supersequence Problem
The Shortest Common Supersequence (SCS) is finding the shortest supersequence Z of given sequences X and Y such that both X and Y are subsequences of Z.
Tag: Bottom-up
Longest Repeated Subsequence Problem
The Longest Repeating Subsequence (LRS) problem is finding the longest subsequences of a string that occurs at least twice.
Longest Palindromic Subsequence using Dynamic Programming
The Longest Palindromic Subsequence (LPS) problem is finding the longest subsequences of a string that is also a palindrome.
Longest Common Substring Problem
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.
Longest Common Subsequence | Finding all LCS
Given two sequences, print all the possible longest common subsequences present in them.
Longest Common Subsequence (LCS) | Space optimized version
This post covers a space-optimized function to find the length of the Longest Common Subsequence (LCS) problem.
Longest Common Subsequence Problem
The Longest Common Subsequence (LCS) problem is finding the longest subsequence present in given two sequences in the same order, i.e., find the 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.
Find maximum sum submatrix present in a matrix
Given an N × N matrix, find the maximum sum submatrix present in it.
Find maximum sum `K × K` submatrix in a given `M × N` matrix
Given an M × N matrix, calculate the maximum sum submatrix of size k × k in it in O(M × N) time.
Calculate the sum of all elements in a submatrix in constant time
Given an M × N matrix and two coordinates (p, q) and (r, s) representing top-left and bottom-right coordinates of a submatrix of it, calculate the sum of all elements present in the submatrix.
Calculate the size of the largest plus of 1’s in a binary matrix
Given a square matrix of 0’s and 1’s, calculate the size of the largest plus formed by 1’s.
Program to find n’th Fibonacci number
Write a program to calculate the nth Fibonacci number where n is a given positive number. Fibonacci’s sequence is characterized by the fact that every number after the first two is the sum of the two preceding ones.