Given two words word1 and word2, find the edit distance between word1 and word2 i.e. minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on … Read More
Dynamic Programming
Find shortest distances between every pair of vertices ( Dynamic Programming Floyd Warshall Algorithm)
Find shortest distances between every pair of vertices in a given edge weighted directed Graph.
Input:
The first line of input contains an integer T denoting the no of test cases . Then T test … Read More
Coin Collection Dynamic Programming
Problem Statement:Coin Collection Dynamic Programming
Given a rectangular grid where each cell contains some coins. You are at the first row and you want to go to the last row with the objective of collecting … Read More
Sequence Finder Dynamic Programming
Sequence Finder
Given two arrays A and B of equal size, you have to determine whether the following the sequence is possible or not.
Subset Sum Problem Dynamic programming
Problem Statement of Subset Sum Dynamic Programming
Given a set T containing a list of integers and a sum S, does a subset of T exists whose sum is equal to S.
NOTE – Subset … Read More
Maximum sum contiguous subarray of an Array
Given an Array A with n integers both positive and negative, find the maximum sum contiguous subarray within A which has the largest sum
Maximum size of square sub matrix with all 1’s in a binary matrix
Maximum size of square sub matrix with all 1
Consider a binary matrix as shown in the figure below. You need to find the maximum size of square sub matrix with all 1’s.
.png)
Edit Distance ( Dynamic Programming )
Problem
Given two strings x and y, What is the cheapest possible way to convert x into y where following operations are allowed to perform –
- Substitute a character c of x with c’.
- Insert
Skiing on Mountains Matrix
Skiing on Mountains Matrix : “John Snow” likes Skiing on Mountains a lot.That’s not very surprising, since skiing is really great. The problem with skiing is one have to slide downwards to gain speed. Also … Read More
The greedy coins game Dynamic Programming
The greedy coins game Dynamic Programming Solution :
Question statement There is a row of 2n coins on the table; each coin can have any positive integer value. Two players alternate turns.
On a player’s … Read More