# 1222. Algorithm - Sequence DPDP

Introduce dynamic programming.

Climbing Stairs Maximum Subarray Longest Increasing Subsequence

## 3. Sequence DP

### 3.1 Fibonacci Numbers

#### 3.1.1 Problem Description

Fibonacci Numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, … Now, given an integer N(N >= 0), return the Nth Fibonacci number.

#### 3.1.2 Recursive Solution

// recursive implementation
public int fibonacci(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}

return fibonacci(n - 1) + fibonacci(n - 2);
}

• Time complexity: $O(2^n)$
• Space complexity: $O(1)$

#### 3.1.3 DP Solution

// DP
public int fibonacci(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}

int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++)  {
dp[i] = dp[i - 1] + dp[i - 2];
}

return dp[n];
}

• Time complexity: $O(n)$
• Space complexity: $O(n)$

#### 3.1.4 Solution with Constant Space

// constant space
public int fibonacci(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}

int first = 0;
int second = 1;
int third = 0;

for (int i = 2; i <= n; i++) {
third = first + second;
first = second;
second = third;
}

return third;
}

• Time complexity: $O(n)$
• Space complexity: $O(1)$

Maximum Subarray

### 3.2 Longest Increasing Subsequence

#### 3.2.1 Problem Description

Given a sequence of integers, find the longest increasing subsequence (LIS). Your code should return the length of the LIS.

Example 1:
Input:  [5,4,1,2,3]
Output:  3
Explanation: LIS is [1,2,3].
Example 2:
Input: [4,2,4,5,3,7]
Output:  4
Explanation: LIS is [2,4,5,7]


#### 3.2.2 DP Solution(n^2)

// O(n^2)
public int longestIncreasingSubsequence(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}

// dp[i], the longest length of LIS which ends at index i.
int[] dp = new int[nums.length];
int max = 0;
for (int i = 0; i < nums.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) { // check 0~i
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
max = Math.max(max, dp[i]);
}

return max;
}

• Time Complexity: $O(n^2)$
• Space Complexity: $O(n)$

Values of the dp array for input A=[4,2,4,5,3,7]. The answer is 4 and the longest increasing subsequence is [2,4,5,7].

A[i]\dp[i] 0 1 2 3 4 5
4 1 0 0 0 0 0
2 1 1 0 0 0 0
4 1 1 2 0 0 0
5 1 1 2 3 0 0
3 1 1 2 3 2 0
7 1 1 2 3 2 4

#### 3.2.3 Binary Search Solution(nlog(n))

Maintain a monotonic increasing array.

// O(nlog(n))
public int longestIncreasingSubsequence3(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}

int[] arr = new int[nums.length]; // increasing array
// 10,9,2,5,3,7,101,18 -> 2,3,7,18
int len = 0;
for (int i = 0; i < nums.length; i++) {
int index = Arrays.binarySearch(arr, 0, len, nums[i]);
if (index < 0) {
index = -(index + 1);
}

arr[index] = nums[i];
if (index == len) {
len++;
}
}

return len;
}

• Time Complexity: $O(nlog(n))$
• Space Complexity: $O(n)$

Values of the dp array for input A=[10,9,2,5,3,7,101,18]. The answer is 4 and the longest increasing subsequence are [2,5,7,101], [2,5,7,18], [2,3,7,101] or [2,3,7,18].

A[i]\arr[i] 0 1 2 3 4 5 6 7
10 10 0 0 0 0 0 0 0
9 9 0 0 0 0 0 0 0
2 2 0 0 0 0 0 0 0
5 2 5 0 0 0 0 0 0
3 2 3 0 0 0 0 0 0
7 2 3 7 0 0 0 0 0
101 2 3 7 101 0 0 0 0
18 2 3 7 18 0 0 0 0

Here, the final array contains the correct LIS . But it is not guaranteed this is always the case. Take another input as example, A=[10,9,2,5,7,3,101,18]. The only difference with the previous input is that 7 and 3 are swapped. The answer is still 4. But the longest increasing subsequence are [2,5,7,101] and [2,5,7,18] only. [2,3,7,101] and [2,3,7,18] are not valid LIS any more, but we have the same final array [2,3,7,18,0,0,0,0] as the previous exmaple.

A[i]\arr[i] 0 1 2 3 4 5 6 7
10 10 0 0 0 0 0 0 0
9 9 0 0 0 0 0 0 0
2 2 0 0 0 0 0 0 0
5 2 5 0 0 0 0 0 0
7 2 5 7 0 0 0 0 0
3 2 3 7 0 0 0 0 0
101 2 3 7 101 0 0 0 0
18 2 3 7 18 0 0 0 0