Dynamic Programming

1. Given a sequence of words, and a limit on the number of characters that can be put in one line (line width). Put line breaks in the given sequence such that the lines are printed neatly. TextJustification.java
2. Find longest bitonic subsequence in an array. Bitonic subsequence first increases and then decreases - BitonicSequence.java Youtube link
3. Given a long word which is made up of multiple words, split the long word into individual words - BreakMultipleWordsWithNoSpaceIntoSpace.java Youtube Link
4. Coin changing problem. Given set of coins and a total t. - CoinChanging.java CoinChangingMinimumCoin.java

• Total solutions possible to form t. Youtube link
• Minimum numbers of coin needed to form t. Youtube link

5. Given a positive integer N, count all possible distinct binary strings of length N such that there are no consecutive 1′s - CountNumberOfBinaryWithoutConsecutive1s.java
6. Count number of trees that can be formed given a preorder sequence - CountNumberOfTreePreorder.java Youtube link
7. Count number of binary search trees formed by an array of size n - CountNumberOfTreesInBST.java Youtube link
8. Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces - CuttingRod.java Youtube link
9. Given n dice each with m faces, numbered from 1 to m, find the number of ways to get sum X. X is the summation of values on each face when all the dice are thrown - DiceThrowWays.java
10. Given two strings of size m, n and set of operations replace (R), insert (I) and delete (D) all at equal cost. Find minimum number of edits (operations) required to convert one string into another - EditDistance.java Youtube link
11. Given number of floors and certain number of eggs, find the floor from which egg will break using minimum number of drops - EggDropping.java Youtube link
12. Given a bag which can only take certain weight W. Given list of items with their weights and price. Stuff these items in the bag such that it maximizes the value of bag - Knapsack01.java Youtube link
13. Given two strings. Find longest common subsequence/substring between the two strings - LongestCommonSubsequence.java Youtube link
14. Given an unsorted array. Find the longest increasing subsequence in this array - LongestIncreasingSubsequence.java Youtube Link
15. Given a sequence, find the length of the longest palindromic subsequence in it - LongestPalindromicSubsequence.java Youtube link
16. Given array of matrices, find a sequence which will have minimum multiplication cost - MatrixMultiplicationCost.java Youtube link
17. Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array - MaxSumForNonAdjacentElements.java
18. Given set of jobs with start and end interval and profit, how to maximize profit such that jobs in subset do not overlap - WeightedJobSchedulingMaximumProfit.java Youtube link
19. Find the longest chain which can be formed from a given set of pairs.In every pair, the first number is always smaller than the second number.Chain of pair (c, d) can follow another pair (a, b) if b < c - MaximumLengthChainPair.java
20. Given a rope of length n meters, cut the rope in different parts of integer lengths in a way that maximizes product of lengths of all parts - MaximumProductCutting.java
21. Given a matrix, find maximum size square sub matrix - MaximumSizeSubMatrix.java Youtube link
22. Given an array of n positive integers. Write a program to find the sum of maximum sum subsequence of the given array such that the integers in the subsequence are sorted in increasing order - MaximumSumSubsequence.java Youtube link
23. Given a cost matrix cost[][] and a position (m, n) in cost[][], write a function that returns cost of minimum cost path to reach (m, n) from (0, 0) - MinCostPath.java Youtube link
24. Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a function to return the minimum number of jumps to reach the end of the array - MinJumpToReachEnd.java Youtube link
25. Given an array of gold coins with different values and two players. Each player picks gold coin from either side. Write an algorithm to maximize your winning chance - NPotGold.java Youtube link
26. Given a matrix. Find total paths to reach from 0,0 to m,n in this matrix - NumberOfPathsInMxNMatrix.java Youtube link
27. Finding the number of ways a given score could be reached for a game with 3 different ways of scoring (e.g. 3, 5 and 10 points) - NumberOfWaysToScorePoints.java
28. Given a sorted array keys[0.. n-1] of search keys and an array freq[0.. n-1] of frequency counts, where freq[i] is the number of searches to keys[i]. Construct a binary search tree of all keys such that the total cost of all the searches is as small as possible - OptimalTreeSearch.java
29. Given a string, partition the string with fewest cuts such that each partition is a palindrome - PalindromePartition.java Youtube link
30. Remove minimum number of elements from either end of array such that 2*min > max in this remaining elements of array - RemoveFromEndToMake2IntoMinGreaterThanMax.java
31. Given a matrix, find a rectangular submatrix with maximum sum - SubRectangularMatrixWithMaximumSum.java
32. Given an array and a total. Tell if elements of this array can form this total - SubsetSum.java Youtube link
33. Given an array of X and Os. Find largest subsquare which is surrounded by Xs - SubsquareSurrounedByXs.java
34. Given three strings, determine if first two strings can interleave to form third string - TwoStringInterleavingToFormThird.java Youtube link
35. Given a number n, find all numbers from 1 to n which are multiples of 2,3 or 5 only. UglyNumbers.java
36. Given the mobile numeric keypad. You can only press buttons that are up,left,right or down to the current button.You are not allowed to press bottom row corner buttons (i.e. * and # ).Given a N find out the number of numbers possible of given length - PhoneDialNumberOfCombinationOfSizeK.java
37. Given a keyboard which only does 4 things, print A, select screen, copy screen and append to screen and given n, how many total As you can print on screen. CountAs.java
38. Given an array, find a sequence of equal length such that sum of each half is same LongestEvenLengthSubstringOffEqualHalf.java
39. Longest common substring between two strings. LongestCommonSubstring.java Youtube link
40. There are N stations on route of a train. The train goes from station 0 to N-1. The ticket cost for all pair of stations (i, j) is given where j is greater than i. Find the minimum cost to reach the destination. MinimumCostTrainTicket.java
41. Fibonacci series FibonacciSeries.java Youtube link
42. Given a 2D array of 0s and 1s, find size of maximum rectangular submatrix - MaximumRectangularSubmatrixOf1s.java
43. Given boxes of different dimensions, stack them on top of each other to get maximum height. But box on top should have strictly less length and width then box under it. BoxStacking.java
44. Given a rod with markings. Cut the rod along markings but reduce the cost of cutting. Cost if cutting is proportional to the length of rod being cut.CutRodToMinimizeCost.java
45. Given two strings, tell if one string is scrambled of another or not. Read question on the code to see what scrambled means. ScrambledString.java
46. Maximize Ski gates passage MaximizeSkiGates.java
47. Given stock prices for certain days how to maximize profit by buying or selling with at most K transactions StockBuySellKTransactions.java stockbuysellktransactions.py
48. Given symbols expression and binary operation result b/w symbols, tell if given expression with any parenthesis combination can produce a given result. SymbolExpressionEvaluation.java symbolexpressionevaluation.py
49. Given expression with +, -, *, / operators, tell if given expression with any parenthesis combination can produce a given result. ExpressionEvaluation.java
50. Given balloons with certain values in what order should you burst them to get max value. BurstBalloons.java
51. Given a 2D matrix, find longest increasing path in this matrix - LongestIncreasingPath.java
52. Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner - Immutable2DSumRangeQuery.java
53. Given a string S and a string T, count the number of distinct subsequences of T in S - DistinctSubsequence.java
54. Dungeon game - DungeonGame.java
55. Find total number of ways to decode a given number - DecodeWays.java
56. 11. Regex matching - RegexMatching.java