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))
// https://www.youtube.com/watch?v=5rfZ4WnNKBk
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 |
3.3 Classic Problems
- LeetCode 70 - Climbing Stairs
- LeetCode 55 - Jump Game
- LeetCode 45 - Jump Game II
- LeetCode 132 - Palindrome Partitioning II
- LeetCode 139 - Word Break
- LeetCode 140 - Word Break II
- LeetCode 674 - Longest Continuous Increasing Subsequence
- LeetCode 300 - Longest Increasing Subsequence
- LeetCode 198 - House Robber
- LeetCode 213 - House Robber II
5. Game, Min-Max
6. Source Files
- Source files for Dynamic Programming on GitHub
- Dynamic Programming Diagrams(draw.io) in Google Drive