Pots of Gold Game – Dynamic Programming

Two-player X and Y are playing Pots of Gold Game where pots of gold arranged in a  line, each containing some gold coins. Both players will get an alternating chance in which the player can pick a pot from one of the ends of the line. The winner is the player who has a higher number of coins at the end. The objective is to … Continue reading Pots of Gold Game – Dynamic Programming

Minimum cost to reach destination – Dynamic Programming

Give n*n matrix find minimum cost required to reach from source to destination. Lets consider source is Array [0][0] and destination is Array [n-1][ n-1] the each elements also represent as cost You can only move down, right and diagonally lower elements from a given element. For example: The path of minimum cost is 1 ->5->1 so minimum cost to reach destination is 7. Dynamic … Continue reading Minimum cost to reach destination – Dynamic Programming

Edit Distance Problem (Levenshtein distance) – Dynamic Programming

There are two strings source and destination. The goal of the problem is to convert source to destination by applying minimum edit operations on string str1. The edit operations are following – Insert Remove Replace For example: We need only one operation to replace char ‘e’ with char ‘o’ Using Recursion Using Dynamic Programming Continue reading Edit Distance Problem (Levenshtein distance) – Dynamic Programming

Longest Increasing Subsequence Problem – Dynamic Programming

Given an array find a subsequence of a given array in which the array’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible Example: From below give array a longest increasing subsequence is This subsequence has length six; the input sequence has no seven-member increasing subsequences. The longest increasing subsequence in this example is not the … Continue reading Longest Increasing Subsequence Problem – Dynamic Programming

Subset Sum Problem – Dynamic Programming

Given a set of positive integers and a value sum write program to determine if there is a subset of the given set with sum equal to given sum. For e.g. subset {4,12,18} has the sum 34 Solution Using Dynamic Programming Approach We will find whether if there is exists any subset of with provided sum 1 if it’s existed store it in array and … Continue reading Subset Sum Problem – Dynamic Programming

Maximum sub array problem – Kadane’s Algorithm

Given a sequence of n real numbers A(1) … A(n), program to find a contiguous subarray with the largest sum For example, var arr = new int[] {-2, 1,-3, 4,-1, 2, 1,-5, 4 }; the contiguous sub array with the largest sum is [4, −1, 2, 1], with sum 6. Solution Solution via iterating over all array elements repeatedly, try each key elements Execute above … Continue reading Maximum sub array problem – Kadane’s Algorithm