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

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

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

🎥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

🎥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

🎥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

- 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📌📌

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

@@ 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📌📌

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

! 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💰 💰

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

+ 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

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

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

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

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

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

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

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

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

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

💛 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

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

Its Okay ! Try Again 💪 👼

Day - 25 📘

Solved: Matrix Chain Multiplication (Recursive)📌 📌

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📗

Solved: Matrix Chain Multiplication (Memoisation)📌 📌

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 💫