Skip to content

Latest commit

 

History

History
569 lines (440 loc) · 28.7 KB

README.md

File metadata and controls

569 lines (440 loc) · 28.7 KB
Raw

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.
🎥Tutorial Link - https://www.youtube.com/watch?v=l02UxPYRmCQ&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go&index=2

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 [ ].
🎥Tutorial Link - https://www.youtube.com/watch?v=kvyShbFVaY8&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go&index=3
🎥Tutorial Link - https://www.youtube.com/watch?v=fJbIuhs24zQ&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go&index=4

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.
🎥Tutorial Link - https://www.youtube.com/watch?v=ntCGbPMeqgg&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go&index=5

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
🎥Tutorial Link - https://www.youtube.com/watch?v=_gPcYovP7wc&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go&index=7
🎥Tutorial Link - https://www.youtube.com/watch?v=_gPcYovP7wc&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go&index=8

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
🎥Tutorial Link - https://www.youtube.com/watch?v=_gPcYovP7wc&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go&index=9

🚶 “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
🎥Tutorial Link - https://www.youtube.com/watch?v=_gPcYovP7wc&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go&index=10

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
🎥Tutorial Link - https://www.youtube.com/watch?v=_gPcYovP7wc&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go&index=11
🎥Tutorial Link - https://www.youtube.com/watch?v=_gPcYovP7wc&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go&index=12

💛 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 @@
🎥Tutorial Link - https://www.youtube.com/watch?v=_gPcYovP7wc&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go&index=13

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
🎥Tutorial Link - https://www.youtube.com/watch?v=_gPcYovP7wc&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go&index=14

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
🎥Tutorial Link - https://www.youtube.com/watch?v=_gPcYovP7wc&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go&index=15
🎥Tutorial Link - https://www.youtube.com/watch?v=_gPcYovP7wc&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go&index=16

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 💫