Tag: dynamicprogramming
-
Data Structures & Algorithms in Java – Dynamic Programming – Unique Paths
Problem: Given a 2 dimensional matrix size m * n , find the number of unique ways to reach the bottom right of the matrix from the top left of the matrix (first cell) if you can move only right or down a step at a time . That is from input[0][0] to input[m-1][n-1] For…
-
Data Structures & Algorithms in Java – Dynamic Programming – Decode Ways
Problem: If A is encoded as 1 , B as 2 and so on until Z as 26 , then find the number of ways a given encoded string can be decoded. For example: The input “121” can be decoded as 1, 2 ,1 (ABA) or 12 1(LA) or 1 21 (AU) So the output…
-
Data Structures and Algorithms in Java – Dynamic Programming – Combination Sum
Problem: Given an array of numbers and a target number , find in how many ways the numbers in the input array can be summed up to form the target number. For example, Given the input: [1,2,3] and the target 4 The output should be 7 since : 1 + 1 + 1 + 1…
-
Data Structures & Algorithms in Java – Dynamic Programming – Jump Game
Problem: Given an array of numbers which indicate how many positions maximum you can jump from that index position , find out if you can reach the end of the array from the beginning. For example: For the input [2,3,1,1,4] You can jump maximum 2 positions from index 0, 3 positions from index 1 ,…
-
Data Structures & Algorithms in Java – Dynamic Programming – House Robber II
Problem: A robber goes to rob in a series of houses built next to each other forming a circle. So the first house and last house are next to each other. The robber cannot steal from consecutive houses as it would trigger an alarm. Find the maximum money the robber can steal. Input: [2,3,2] Each…
-
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]…
