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
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
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
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
Find nth fibonacci number. The Fibonacci Sequence is the series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … The next number is found by adding up the two numbers before it. Let F[i] be the ith fibonacci number Solution using Recursion Solution Dynamic Dynamic Programming Continue reading Fibonacci Numbers Problem – Dynamic Programming
Given a rod of size n and values of various sizes of rod. The problem is to cut the rod in such a way that the sum of values of the pieces is maximum. For e.g. will consider size of rod is length of arr here i.e.5. Size’s of the road are 1,2,3,4,5 respectively. So, we can cut the rod in various ways like To … Continue reading Rod Cutting 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
The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. Given weights and values of n items, put these items … Continue reading Knapsack Problem
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
Problem A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. Given an array of stones (non-negative integers) where each element in the array represents the maximum number of positions one can move forward from that element. Write a program to Find the minimum number of jumps required to cross … Continue reading Frog Jump Problem
