This is a C++ Program to implement the Floyd Warshall Algorithm using Dynamic Programming technique. Problem Description Find shortest distance between each pair of vertices in the given graph. This problem is also known as All pairs shortest path problem. Problem Solution One solution to this problem is to apply Dijkstra algorithm for all vertices. … Read more
This is a C++ Program that Solves Bellman Ford Algorithm using Dynamic Programming technique. Problem Description Given a weighted graph and a source vertex. Find the shortest path from the source to all the vertices. The graph may contain edges with negative value. Problem Solution This is a single source shortest path problem. We know … Read more
This is a C++ Program that Solves Make Palindrome Problem using Dynamic Programming technique. Problem Description You are given a string str. Find the minimum number of characters to be inserted to string str to convert it to a palindrome. Problem Solution This problem is a variation of the longest common subsequence problem. First, find … Read more
This is a C++ Program that Solves Length of Longest Arithmetic Progression Problem using Dynamic Programming technique. Problem Description Given sorted array of integers, find the Length of the Longest Arithmetic Progression (LLAP) in it. Problem Solution If elements a,b,c,d,e are in AP, then b=(a+c), c=(b+d), d=(c+e). Also, c=(a+e). We will be using this observation … Read more
This is a C++ Program that Solves the Stock Market Problem using Dynamic Programming technique. Problem Description Given the price of share on n days, find the maximum profit that you can make by buying and selling a share at most twice. Problem Solution In this problem, we are required to find the maximum obtainablem … Read more
This is a C++ Program that Solves Building Problem using Dynamic Programming technique. Problem Description There are n plots in a row. Buildings are to be constructed on these plots in such a way that there is space between every two buildings. Find the number of ways in which buildings can be constructed in the … Read more
This is a C++ Program that Solves Longest Palindromic Subsequence Problem using Dynamic Programming technique. Problem Description You are given a string str. Find the length of longest palindromic subsequence in the given string. Problem Solution This problem is a variation of the longest common subsequence problem. The required result is simply the LCS of … Read more
This is a C++ Program that Solves Sum of Digits Problem using Dynamic Programming technique. Problem Description Given a number n, find the sum of digits of all numbers from 1 to n. Problem Solution To solve this problem in an efficient manner, we will calculate the sum in a pattern. If we are given … Read more
This is a C++ Program that Solves Minimum Number of Squares Problem using Dynamic Programming technique. Problem Description It is always possible to represent a number in the form of sum of squares of numbers. For example – 15= 3^2 + 2^2 + 1^2 + 1^2 Given a number x, find the minimum number of … Read more
This is a C++ Program that Solves Shortest Common Subsequence Problem using Dynamic Programming technique. Problem Description You are given two strings. Find the length of the shortest string that has both the given strings as subsequences. Problem Solution We can solve this problem by using bottom up DP. We will process the strings character … Read more
