[LeetCode][300. Longest Increasing Subsequence] 3 Approaches: Backtrack, DP, Binary Search
By Long Luo
This article is the solution 3 Approaches: Backtrack, DP, Binary Search of Problem 300. Longest Increasing Subsequence.
Here shows 3 Approaches to slove this problem: Backtrack, DP, Binary Search.
Backtrack
The Brute Force approach, there are \(2^n\) subsequences, use Backtrack to find the answer.
TLE!1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30class Solution {
int minCount = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount) {
if (amount <= 0) {
return 0;
}
minCount = Integer.MAX_VALUE;
dfs(coins, amount, 0);
return minCount == Integer.MAX_VALUE ? -1 : minCount;
}
private int dfs(int[] coins, int remain, int count) {
if (remain < 0) {
return -1;
}
if (remain == 0) {
minCount = Math.min(minCount, count);
return count;
}
for (int x : coins) {
dfs(coins, remain - x, count + 1);
}
return -1;
}
}
Analysis
- Time Complexity: \(O(2^n)\)
- Space Complexity: \(O(n)\)
DP
The equation:
\(dp[i] = \textit{max}(dp[j]) + 1, 0 \leq j < i and \textit{nums}[j] < \textit{nums}[i]\).
1 | class Solution { |
Analysis
- Time Complexity: \(O(n^2)\)
- Space Complexity: \(O(n)\)
Binary Search
1 | class Solution { |
Analysis
- Time Complexity: \(O(nlogn)\)
- Space Complexity: \(O(n)\)
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗