---
# System prepended metadata

title: 'DP 2: Famous Problems'

---

# DP 2: Famous Problems

---
title: Problem 1 Longest Increasing Subsequence
description:
duration: 600
card_type: cue_card
---

### Problem Statement

Given an Integer array of size N.

Find length of Longest Increasing Subsequence

**Input:**
A = [1, 3, 2, 3, 1, 5]


**Explanation:**
All possible increasing subsequences are [1, 2], [1, 3], [1, 3, 5], [1, 5], [1, 2, 3], [1, 2, 3, 5].

Among this, [1, 2, 3, 5] is the longest, with length 4.


**Output:**
4




---
title: Longest Increasing Subsequence Approach
description:
duration: 600
card_type: cue_card
---

### Brute Force Approach

* Generate all possible subsequences (Cost : 2$^N$)
* Check if the subsequences is increasing
* Among all possible increasing subsequences, take the maximum length.


<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/914/original/a.png?1725816805" width=500px/>

Lets take an example,

A = [1, 3, 2, 3, 1, 5]


The subsequence is formed, based on the below condition.

Once 5 is selected, then the elements to its left, is less than 5.

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/915/original/a.png?1725816848" width=500px/>


On each recursion call, we have (current_element, constrait).



If we select the number in which the constraint also has to get satisfied.

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/916/original/a.png?1725816884" width=500px/>


1D Recursion

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/917/original/a.png?1725816925" width=500px/>


### Observation

Choices for 2nd last element

1. Elements of Choices --> All elements has that A[i] in the left of i.
3. Recursive State
llis(i) --> Length of  Longest Increasing  Subsequence Ending on index i(A[i])


3. Recurrance Relationship
llis (i) = 1+ max(llis(j) if(A[j] < A[i]))

4. which state is ans?
llis (N-1)? No

for all i -> 0 to N - 1



### Pseudo Code

Brute Force
```java
int length = 1;

int llis (A, i) {

   if (i == 0) { return 1;}
     ans = 1;
     for (j = i - 1; j > 0; j--){
         if (A[j] > A[i]){
             ans = max(ans, 1 + llis(j);
         }
     }
     
   length = max (length, ans);
   return ans;
}
```
### Complexity

**Time Complexity**: O(N!)

### Optimised Approach

We can simply store the each states using the DP.

Recursive Approach (Top Down Approach)


### Pseudo Code

```java
int DP[N] = {-1}

int llis(A,i){
   if(i == 0){return 1;}
   if(DP[i]! = -1){return DP[i];}
   ans = 1;
   for(j = i - 1; j > 0; j--){
      if(A[j] < A[i]){
         ans = max(ans, llis(j));
      }
      
   }
   DP[i] = ans;
   return ans;
}
```
### Complexity

**Time Complexity**: (N) * (N) = O(N2)

**Space Complexity**: O(N + N) = O(N)



**Iterative (Bottom Up)**

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/918/original/a.png?1725816973" width=500px/>


### Pseudo Code

```java
int DP[N];
DP[0] = 1;

for(i = 1; i < N; i++){
   ans = 1;
   for(j = 0; j < i; j++){
       if(A[j] < A[i]){
          ans = max(ans, 1 + DP[j]);
       }
   }
   DP[i] = ans;
}

ans = DP[0];
for(i = 1; i < N; i++){
   ans = max(ans, DP[i]);
}
return ans;
```

### Complexity

**Time Complexity**: O(N$^2$)
**Space Complexity**: O(N)




---
title: Problem 2 Russian Doll Envelope
description:
duration: 600
card_type: cue_card
---

### Problem Statement

Given N Envelopes, where
L[i] => Length of ith Envelope
W[i] => Width of ith Envelope

Find maximum number of envelopes we can put one into the other


When can you put Envelope 2 into 1?
> l2 < l1  && w2 < w1

Example 1:
L = [5 6 6 2]
w = [6 4 7 3]

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/906/original/a.png?1725815859" width=300px/>


Example 2:

L = [3, 2, 1, 3]
W = [2, 3, 1, 3]

Answer : 2

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/907/original/a.png?1725815940" width=300px/>



### Solution Approach

1. **Brute Force**

Find all possibe subsequence and check if it possible to put one into the other.

2. Optimised Approach

Lets take the previous example

L = [5 6 6 2]
w = [6 4 7 3]

Now, pick the solution sequence alone, and Think of how we would find the order in which the envelopes are put one after another.

Since sorting the sequence is optimal to find the order.


Do we have to sort each subsequence separately?

> No, we can sort the entire  


* Sort the Envelopes (on width or length)

<img src ="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/899/original/a.png?1725814266" width = 500px/>

Width is already sorted


Figure out Envelopes on the basis of length such that length is in increasing ? 

> Longest Increasing Subsequence

### Pseudo Code

```java
DP[0] = 1;

for(i = 1; i < N; i++){
   ans = 1;
   for(j = 0; j < i; j++){
       if(L[j] < L[i] && W[j] < W[i]){
          ans = max(ans, 1 + Dp[j]);
       }
   }
   DP[i] = ans;
}
ans = DP[0];
for(i = 1; i < N; i++){
   ans = max(ans, Dp[i]);
}
return ans;
```

---
title: Problem 3 Palindrome Substring
description:
duration: 600
card_type: cue_card
---

### Problem Statement


Given a String of size N.

for all pair(i,j) check if substring S[i,j] is a palindrome.?

**Example:**

S = babad


<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/900/original/a.png?1725814375" width = 300px/>



<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/901/original/a.png?1725814484" width = 300px/>




Solution

1. Brute Force

For all Substring => Check if it is a palindrome or not.

O(N$^2$) * O(N) = O(N$^3$)


2. Optimised Solution

As we can see that, whenever we are checking for a palindrome for a substring(i, j), We check for (i + 1, j - 1).

Here, we tabulate the above mentioned checking.


<img src ="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/902/original/a.png?1725814586" width=500px/>


As we can see that, there are many repetitions present in it.


Also we will check with the length one by one.

L = 1
L = 2
L = 3
.
.
L = N

The answer for this, also lies in the table only.


<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/903/original/a.png?1725814687" width=500px/>




### Complexity

**Time Complexity**: O(N$^2$)


---
title: Problem 4 Palindromic Partition
description:
duration: 600
card_type: cue_card
---

### Problem Statement


Find minimum number of cuts required in a string to make all portions a palindrome.

S = a| b| a| b| a| a


**Possible cuts:**

a|b a b|a a
a|b a b|a|a
a b a b a|a  => 1

Answer: 1


### Observation

1. Brute Force

a |b |a |b |a |a

We have the notion of choices, for a String of size N, we have N - 1 possible cuts.


We use Backtracking with Memoisation to store each recursive calls. 



<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/904/original/a.png?1725814793" width=500px/>