Target Sum

“Target Sum” is a special problem for all the DPHolics I have with me today. There ain’t no need to worry I am going to abandon the rest of my lovely readers. We all have gone through the classic KnapSack problem where we try to find the maximum number of …

Read moreTarget Sum

Longest Common Subsequence

You are given two strings str1 and str2, find out the length of the longest common subsequence. Subsequence: a subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For ex ‘tticp‘ is the subsequence …

Read moreLongest Common Subsequence

House Robber

The House Robber Problem states that, in a neighborhood in a city, there is a single row of n houses. A thief is planning to carry a heist in this neighborhood. He knows how much gold is concealed in each of the houses. However, in order to avoid triggering an …

Read moreHouse Robber

Pascal Triangle Leetcode

The Pascal Triangle is a very good Leetcode problem that is asked so many times in Amazon, Microsoft, and other companies. we have given non-negative integer rows, print first rows rows of the pascal triangle. Example rows = 5 rows = 6 Types of solution for Pascal Triangle Leetcode Dynamic Programming …

Read morePascal Triangle Leetcode

Palindrome Partitioning

Palindrome Partitioning is a DP problem. In this problem, Given a string S. Partition S such that every substring of the partition is a palindrome.  We need to print the minimum cuts needed for a palindrome partitioning of S. Input Format Only a single line containing string S. Output Format …

Read morePalindrome Partitioning

New 21 Game

New 21 Game is a problem that is based on the card game “21”. The problem statement of this problem is simple. We are initially having 0 points. If the value of our current points is less than K points then we draw numbers. During each draw we gain an …

Read moreNew 21 Game

Distinct Subsequences

Given two strings S and P1, we have to count all the number of distinct subsequences of S which equals P1. Note: A subsequence of a given string is a string that we archive by deleting some characters or possible zero characters also from the original string. We can’t change …

Read moreDistinct Subsequences

Subset sum problem

In the subset sum problem, we are given a list of all positive numbers and a Sum. We need to check if there is a subset whose sum is equal to the given sum. Example Input List of numbers: 1 2 3 10 5 sum: 9 Output  true Explanation  for …

Read moreSubset sum problem

Ugly Numbers

The positive numbers whose only prime factors are 2, 3, or 5 are known as ugly numbers. For eg- 8 is an ugly number because it’s an only prime factor is 2 but 7 is not an ugly number because it’s a prime factor is 7. 1 being an exception …

Read moreUgly Numbers