# DP 2: Famous Problems

---
### Problem 1 Longest Increasing Subsequence

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

---

### 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.


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.


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

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


1D Recursion


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

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

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)**


### Pseudo Code

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)

---
### Problem 2 Russian Doll Envelope

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://hackmd.io/_uploads/Bk2-VVPx0.png" width=300px/>

Example 2:

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

Answer : 2

<img src="https://hackmd.io/_uploads/HJLtw4DeR.png" 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)


Width is already sorted

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

> Longest Increasing Subsequence

### Pseudo Code

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;

---
### Problem 3 Palindrome Substring

Given a String of size N.

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

**Example:**

S = babad



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.


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.


### Complexity

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

---
### Problem 4 Palindromic Partition

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.