Skip to content

Sharing my 30 days long journey πŸ’œ of Dynamic Programming πŸ’« πŸ”₯ . This would not be possible without Aditya Verma's DP series πŸ™ πŸ‘‡ πŸ‘‡

Notifications You must be signed in to change notification settings

kothariji/30-days-of-Dynamic-Programming

Folders and files

NameName
Last commit message
Last commit date

Latest commit

Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 

Repository files navigation

Dynamic Programming πŸš€πŸš€

CP is OP ❀️ Saying hi to DP! πŸ”₯πŸ”₯



Definition : πŸ“™

Simply cached Recursion (Memoization) or in other words enhanced recursion.
The main idea behind DP is to store the results of subproblems so that we can simply use the results of these subproblems without re-computing them when needed in the future. This idealogy saves a lot of time and makes the solution optimized.

Day - 1 πŸ“˜

Knapsack Problem: πŸ“ŒπŸ“Œ

In this problem we are given an empty bag with its maximum weight holding capacity. Also, we are given a list of items with there weight and profit values. We need to find out the maximum profit we can earn.

Type of Knapsack Problems

  • Fractional Knapsack - It is simply a greedy problem. In this, we can take fraction values. for eg. if we have space of 3 kg. left in a knapsack and we have an item of 6 kg that values 50 rs. , then we can take 50% of that item and we will gain a profit of 25 rs.

  • 0/1 Knapsack - It is a classical DP problem. Many beginner-level problems are a variation of this problem. In this, we have only had two choices, either we include the item in Knapsack or we don't.

  • Unbounded Knapsack - It is similar to 0/1 Knapsack but in this, we can include the same item multiple numbers of times.

! solved a classical knapsack problem using only recursion.

It all started with Day-1 πŸ”₯πŸ”₯


Day - 2 πŸ“—

Memoization: Top - Down Approach πŸ“ŒπŸ“Œ

It is an optimization technique used to cache the results of subproblems so that we can use that results later on if required. Memoization ensures that a method doesn't run for the inputs whose results are previously calculated.

The dimensions of the memoization array/table depend upon variables. If in recursive function:

  • 1 variable is changing on recursive call, we will create a linear vector/array. E.g. Fibonacci series
  • 2 variables are changing on recursive call, then we will use a 2-D matrix to store the results of subproblems. E.g. Longest Common Subsequence
  • and so on.....for 3, 4..n variables.

Generally we should initialize these matrices with -1 and later on we can check that if the value of a particular cell is not -1 then we will directly return that particular cell value. else we will do a recursive call and set the cell value and finally return the cell value.

+ solved a classical knapsack problem using the memoization technique.

Problem solved

Platform Title Solution Difficulty
GEEKSFORGEEKS 0 - 1 Knapsack Problem View Solution Easy
Important Tip -  std::vector's at() function is similar to subscript operator [ ].
But when the performance is measured at() function is 3.1 times faster then subscript operator [ ]. 

This costed me 29 submissions 😣 πŸ˜†


Day - 3 πŸ“’

1. Tabulation: Bottom-Up Approach πŸ“ŒπŸ“Œ

It is one of the most preferable methods in dynamic programming. It is faster than the memoization method as it doesn't involve any recursive calls. In this method, we have an array/matrix and we start from the first cell and move down filling entries in each cell one by one.

2-Steps to create dp matrix.

  • Step-1 Initialisation - It is similar to the base condition which we do in a recursive function. for eg.
//in recursive function
    if((index <0)|| (w <= 0))
   		return 0;

//in bottom-up approach
   for(int i =0; i<=n; i++){
   		for(int j= 0; j<=w; j++){
   			if(i == 0 || j ==0)
   			    dp[i][j] = 0;
   			}
   		}
  • Step-2 Iterative Function - We create an iterative function that is similar to the recursive call function. All the conditions will be the same in both the methods, the only difference is that in memoization we do recursive calls whereas in the bottom-up approach we look up for previous cells in the matrix, this makes bottom-up approach a faster approach.
- solved the classical knapsack problem using bottom-up approach.

Problem solved

Platform Title Solution Difficulty
SPOJ KNAPSACK - The Knapsack Problem View Solution Easy
Important Tip -  The bottom-up approach is preferred over memoization because in the memoization technique 
we might get stack overflow on doing various recursive calls for large data.

Though it's a rare condition. πŸ˜…πŸ˜…


Day - 4 πŸ“•

Solved: Subset Sum Problem πŸ“ŒπŸ“Œ

It is a variation of the knapsack problem in which we are given an array of non-negative integers and a required sum. We need to find out that is it possible to create a subset of that array so that sum of elements of the subset equals the required sum.

@@ solved the subset sum problem @@

Problem solved

Platform Title Solution Difficulty
SPOJ PARTY - Party Schedule View Solution Easy
GEEKSFORGEEKS Subset Sum Problem View Solution Medium
LEETCODE Partition Equal Subset Sum View Solution Medium

Finally DP started showing it's colors. πŸ’›πŸ’™πŸ’œπŸ’šβ€οΈ


Day - 5 πŸ““

Solved: Count of Subsets with Required Sum πŸ“ŒπŸ“Œ

It is a slight variation of the Subset Sum Problem in which we are given an array of non-negative integers and a required sum. We need to find out the count of the total number of subsets of the given array whose sum equals the required sum.

! solved the Count of Subsets with Required Sum Problem

Problem solved

Platform Title Solution Difficulty
GEEKSFORGEEKS Perfect Sum Problem View Solution Medium

🚢 β€œI walk slowly, but never backwards.” 🚢 - β€” Abraham Lincoln πŸ™ πŸ™


Day - 6 πŸ“™

Solved: Minimum Sum Partition Problem πŸ“ŒπŸ“Œ

Again its a variation of the Subset Sum Problem. The problem statement states that we are given an array with non-negative integers and our task is to divide the elements of that array into two subsets such that the absolute difference between their sums is minimum.

+ solved the subset sum problem

Problem solved

Platform Title Solution Difficulty
GEEKSFORGEEKS Minimum sum partition View Solution Hard

Some days are harder than others πŸ˜– 🚩 😌


Day - 7 πŸ“˜

Solved: Count of Subsets with required difference πŸ“ŒπŸ“Œ

This is a variation of Minimum Sum Partition Problem interesting problem. In this, we are given an array with non-negative integers and our task is to divide the elements of that array into two subsets such that the absolute difference between their sums equals required difference.

Two equations to solve the problem are:
 s1 = sum of 1st subset
 s2 = sum of 2nd subset
 S = required difference
 range = sum of entire array


 s1 - s2 = S 			//equation 1
 s1 + s2 = range		//equation 2

 // on solving eq1 and eq2 we get
 s1 = (range + S)/2
Target sum - It's an awesome problem. Must try:- https://leetcode.com/problems/target-sum/

Problem solved

Platform Title Solution Difficulty
INTERVIEW BIT Minimum Difference Subsets! View Solution Hard
LEETCODE Target Sum πŸš€ View Solution Hard
- solved count of subsets with given difference

πŸ’› 7-Days Streak. πŸ’™ 7-Days of CP. πŸ’œ 7-Days of DP πŸ’š 7-Days of OP ❀️


Day - 8 πŸ“—

Solved: Unbounded Knapsack:pushpin::pushpin:

Unbounded Knapsack Problems are slightly different from 0/1 Knapsack Problems. In this, we can include the same item multiple numbers of times inside the knapsack and our aim is to just maximize the profit.

We just need to change one condition:
//0-1 Knapsack
if(weight[i-1] <= j)
dp[i][j] = max((value[i-1] + dp[i-1][j-weight[i-1]]), dp[i-1][j]);

// Unbounded Knapsack
if(weight[i-1] <= j)
dp[i][j] = max((value[i-1] + dp[i][j-weight[i-1]]), dp[i-1][j]);

Problem solved

Platform Title Solution Difficulty
HACKERRANK Knapsack View Solution Medium
GEEKSFORGEEKS Knapsack with Duplicate Items View Solution Medium
@@ solved Unbounded Knapsack Problem @@

Visited HackerRank after so Long ! Nostalgic πŸ’« πŸ˜„


Day - 9 πŸ“’

Solved: Rod Cutting Problem:pushpin::pushpin:

Problem Statement: Given a rod of length n and an array of prices that contains prices of all pieces of size ranging from 1 to n. Determine the maximum value obtainable by cutting up the rod and selling the pieces.

Problem solved

Platform Title Solution Difficulty
GEEKSFORGEEKS Reach a given score View Solution Easy
GEEKSFORGEEKS Rod Cutting View Solution Easy
! solved Rod Cutting Problem

Set Goals. 🌟 Say Prayers. πŸ™ Work Hard. πŸ’ͺ


Day - 10 πŸ“•

Solved: Coin Change Problem:moneybag: :moneybag:

Problem Statement: You are given a value N and array of coins. You need to find out the number of ways in which you can get value N from that coins. There is infinite supply of coins.(Unbounded Knapsack πŸ˜‰)

Problem solved

Platform Title Solution Difficulty
GEEKSFORGEEKS Coin Change View Solution Medium
HACKERRANK The Coin Change Problem View Solution Medium
LEETCODE Coin Change 2 View Solution Medium
+ solved Rod Cutting Problem

Prove Them Wrong πŸ˜‰ πŸ˜‰


Day - 11 πŸ““

Solved: Maximize The Cut Segments Problem πŸ“Œ πŸ“Œ

Problem Statement: Given an integer N denoting the Length of a line segment. you need to cut the line segment in such a way that the cut length of a line segment each time is integer either x, y, or z. and after performing all cutting operations the total number of cut segments must be maximum.

- solved Coin Change 2 Problem

Problem solved

Platform Title Solution Difficulty
GEEKSFORGEEKS Maximize The Cut Segments View Solution Easy
LEETCODE Coin Change View Solution Medium
GEEKSFORGEEKS Number of Coins View Solution Medium
Important Tip -  This is a unique problem of Knapsack Family. 
In this, we have to initialize 2nd row as well.
for(int i =1; i<amount+1;i++)
{
	if(i%coins[0] == 0)
		dp[1][i] = i/coins[0];
	else
		dp[1][i] = INT_MAX -1;
}

Finally, struggled for 3 days to solve Maximize The Cut Segments 😌 😌


Day - 12 πŸ“™

Longest Common Subsequence πŸ“Œ πŸ“Œ

Problem Statement: Given two strings s1 and s2, find the length of the longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.

@@ solved Longest Common Subsequence using Recursion @@

The longest common subsequence problem is a classic computer science problem, the basis of data comparison programs such as the diff utility, and has applications in computational linguistics and bioinformatics. πŸš€πŸš€πŸš€

Believe me! You are awesome! 😊


Day - 13 πŸ“˜

Solved: # Longest common subsequence Memoization πŸ“Œ πŸ“Œ

Did the LCS problem using the Bottom-up approach(Memoisation).

! solved Longest Common Subsequence using Memoization

Problem solved

Platform Title Solution Difficulty
GEEKSFORGEEKS Longest Common Subsequence View Solution Medium

It was the most challenging day to maintain streak 😞 😞


Day - 14 πŸ“—

Solved: # Longest common subsequence Tabulation πŸ“Œ πŸ“Œ

Did the LCS problem using the Top-Down approach(Tabulation ).

+ solved Longest Common Subsequence using Tabulation. 

Problem solved

Platform Title Solution Difficulty
LEETCODE Longest Common Subsequence View Solution Medium

Be Savage. Not Average πŸ”₯ πŸ˜‰ πŸ’₯


Day - 15 πŸ“’

Solved: Longest Common Substring πŸ“Œ πŸ“Œ

Problem Statement: Given two strings s1 and s2. The task is to find the length of the longest common substring.

Subarray vs Substring vs Subsequence

  • A subarray is a contiguous sequence of elements within an array. For example, the subarrays of the array {1, 2, 3} would be {1}, {2}, {1, 2}, {2, 3}, {1, 2, 3}, {}.
  • A substring is exactly the same thing as a subarray but in the context of strings. For example, the substrings of the string "dhruv" would be "d", "dh", "ru", "uv", "hruv", "hru", "dhru", "ruv", "hr", "", etc.
  • A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the subsequenceof the string "dhruv" would be "d", "du", "rv", "dhv", "hrv", "drv", "dhru", "dv", "v", "", etc.
- solved the Longest Common Substring.

Problem solved

Platform Title Solution Difficulty
LEETCODE Maximum Length of Repeated Subarray View Solution Medium
GEEKSFORGEEKS Longest Common Substring View Solution Medium

Let the streak going. Don't give a <br /> πŸ˜† πŸ˜†


Day - 16 πŸ“•

Solved: Printing LCS πŸ“Œ πŸ“Œ

Problem Statement: Given two strings s1 and s2, print the longest subsequence present in both of them. It's a unique question as in this question we need to traverse back into our DP array and check for positions where characters are matching

string s1 = "coding";
string s2 = "cubing";
--------------------------
dp array 
     c o d i n g
   0 0 0 0 0 0 0 
    \
c  0 1 1 1 1 1 1
     | 
u  0 1 1 1 1 1 1
     | 
b  0 1-1-1 1 1 1
          \ 
i  0 1 1 1 2 2 2
            \
n  0 1 1 1 2 3 3
              \ 
g  0 1 1 1 2 3 4
---------------------------
output => cing
@@ solved the Printing LCS. @@

Problem solved

Platform Title Solution Difficulty
HACKERRANK The Longest Common Subsequence View Solution Medium

I'd Rate My Programming Puns C++ 😏 😏


Day - 17 πŸ““

Solved: Shortest Common Supersequence πŸ“Œ πŸ“Œ

Problem Statement: Given two strings str1 and str2, find the length of the smallest string which has both, str1 and str2 as its sub-sequences.

! solved Shortest Common Supersequence. 

Problem solved

Platform Title Solution Difficulty
GEEKSFORGEEKS Shortest Common Supersequence View Solution Easy

A rabbit aims for the moon πŸ˜•


Day - 18 πŸ“™

Solved: Minimum Number of Deletions and Insertions πŸ“Œ πŸ“Œ

Problem Statement: Given two strings str1 and str2. Your task is to convert str1 to str2. You can only perform two types of operations that are remove or insert. Find the minimum number of operations required to convert str1 into str2.

+ solved Minimum Number of Deletions and Insertions. It's a simpler version of classical Edit Distance Problem 

Problem solved

Platform Title Solution Difficulty
GEEKSFORGEEKS Minimum number of deletions and insertions View Solution Easy

Please Don't Let Your Dreams Die πŸ™ πŸ™


Day - 19 πŸ“˜

Solved: Longest Palindromic Subsequence πŸ“Œ πŸ“Œ

Problem Statement: Given a string str1. Your task is to find the Longest Palindromic Subsequence of that string s1..

- solved Longest Palindromic Subsequence. 

Problem solved

Platform Title Solution Difficulty
GEEKSFORGEEKS Longest Palindromic Subsequence View Solution Easy
LEETCODE Longest Palindromic Subsequence View Solution Medium
INTERVIEWBIT Longest Palindromic Subsequence View Solution Medium

Be Different. Be Awesome. πŸ˜‰ πŸ’«


Day - 20 πŸ“—

Solved: Minimum Deletions to make string Palindromic πŸ“Œ πŸ“Œ

Problem Statement: Given a string of s1. Your task is to remove or delete minimum number of characters from the string so that the resultant string is palindrome.

@@ solved Minimum Deletions to make string Palindromic. @@

Problem solved

Platform Title Solution Difficulty
GEEKSFORGEEKS Minimum Deletions View Solution Easy

Stay Patient. Trust your journey. 😌 πŸ“


Day - 21 πŸ“’

Solved: Printing Shortest Common Supersequence πŸ“Œ πŸ“Œ

Problem Statement: Given two strings str1 and str2, print the smallest string which has both, str1 and str2 as its sub-sequences.

! solved Printing Shortest Common Supersequence.

Problem solved

Platform Title Solution Difficulty
LEETCODE Shortest Common Supersequence View Solution Hard

πŸ’› 21-Days Streak. πŸ’™ 21-Days of CP. πŸ’œ 21-Days of DP πŸ’š 21-Days of OP ❀️


Day - 22 πŸ“•

Solved: Longest Repeating Subsequence πŸ“Œ πŸ“Œ

Problem Statement: Given a string s, find the length of the longest repeating SubSequence such that the two subsequences don’t have the same string character in the same position, i.e., any i’th character in the two subsequences shouldn’t have the same index in the original string.

+ solved Longest Repeating Subsequence.

Problem solved

Platform Title Solution Difficulty
GEEKSFORGEEKS Longest Repeating Subsequence View Solution Easy
INTERVIEWBIT Repeating Sub-Sequence View Solution Medium

Hey ! We are still at Day-0! 😌 😌


Day - 23 πŸ““

Solved: Is Subsequence ? πŸ“Œ πŸ“Œ

Problem Statement: Given two strings str1 and str2, check if str1 is subsequence of str2..

- solved Is Subsequence ?
Important Tip -  This question can be solved in O(n) time complexity without DP also. But still DP  is Awesome.
Approach: Simpply we can apply LCS on both str1 and str2, 
and then we can check that the Length of LCS is equals to s1 or not.

if(dp[n][m] == s1.length())
	return true;
else
	return false;

LIVE πŸ’« LAUGH πŸ˜† CODE πŸ’»


Day - 24 πŸ“™

Solved: Minimum Insertion Steps to Make a String Palindrome πŸ“Œ πŸ“Œ

Problem Statement: Given a string s, find the minimum number of insertion operations you could perform on the string to make the string palindromic.

@@ solved Minimum Insertion Steps to Make a String Palindrome. @@

Problem solved

Platform Title Solution Difficulty
GEEKSFORGEEKS Form a palindrome View Solution Medium
LEETCODE Minimum Insertion Steps to Make a String Palindrome View Solution Hard
SPOJ IOIPALIN - Palindrome 2000 View Solution Medium

Its Okay ! Try Again πŸ’ͺ πŸ‘Ό


Day - 25 πŸ“˜

Solved: Matrix Chain Multiplication (Recursive):pushpin: :pushpin:

Problem Statement: Given an array p[] which represents the chain of matrices such that the ith matrix Ai is of dimension p[i-1] x p[i]. We need to write a function that should return the minimum number of multiplications needed to multiply the chain.

Optimal Substructure Solution:
In this approach, we can place parenthesis at all possible places and then calculate the cost, and finally, we can find the minimum value. For example, if the given chain is of 4 matrices. let the chain be ABCD, then there are 3 ways to solve: (A)(BCD), (AB)(CD), and (ABC)(D). So when we place a set of parentheses, we divide the problem into subproblems of smaller size. Therefore, the problem has optimal substructure property and can be easily solved using recursion.

! solved Matrix Chain Multiplication (Recursive).

If you avoid difficult things, great things will avoid you πŸ’« πŸ’š


Day - 26:green_book:

Solved: Matrix Chain Multiplication (Memoisation):pushpin: :pushpin:

Problem Statement: Given an array p[] which represents the chain of matrices such that the ith matrix Ai is of dimension p[i-1] x p[i]. We need to write a function that should return the minimum number of multiplications needed to multiply the chain.

Just 4 more lines of code....and πŸ’₯πŸ’₯πŸ’₯ now your code is Memoised. ❀️

+ solved Matrix Chain Multiplication (Memoisation).

Those Who Cannot Remember the Past are Condemned to Repeat It πŸ˜† πŸ˜† ~ Dynamic Programming πŸ’«