Category: Dynamic Programming
-
Data Structures & Algorithms in Java – Dynamic Programming – Longest Common Subsequence
Problem: Given two strings , find the longest common subsequence between them. For example , Consider the input: “abcde” and “ace” The longest common subsequence between them is “ace”. A subsequence is just a sequence of characters from the original string with any characters removed and the order of remaining elements unchanged. Try out the…
-
Data Structures & Algorithms in Java – Dynamic Programming – Longest Increasing Subsequence
Problem: Given an array of integers , find the length of the longest increasing subsequence. Example: Given the input: [10,9,2,5,3,7,101,18] The longest subsequence is [2,3,7,101] , so output is length 4 A subsequence is just a sequence of numbers from an array where you can remove numbers at any position. Increasing subsequence means the numbers…
-
Data Structures & Algorithms in Java – Dynamic Programming- Minimum Coin Change
Problem: Given a set of coins and an amount , find the minimum set of coins required to compute that amount. For example , If you are given the set of coins 1,2 and 5 ,you need to compute the number of coins required to calculate the amount of 11 rupees. Input: Coins = [1,2,5]…
-
Data Structures & Algorithms – Dynamic Programming – Climbing Stairs
Problem: Given a step number in a stair case , find the number of ways you can reach that step in the staircase if you can make 1 or 2 steps at a time Input: 4 Output: 5 ways Since you can take any of the below sequence of steps: [1,1,1,1] , [1,2,1],[1,1,2] ,[2,1,1], [2,2]…