Last active
October 31, 2020 16:14
-
-
Save liyunrui/162d6ab530bfa9a2c9e9d2fc2e74397d to your computer and use it in GitHub Desktop.
leetcode-dp
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution: | |
""" | |
Problem Clarification | |
-We must ask interviewer to go through the examples. | |
-You can even go through another examples to make sure there's no misunderstanding. | |
-Ask edge case, input and output data structure, sorted or not sorted, Positive or Negative? | |
duplicates? | |
strictly increasing? | |
Thought Process | |
If we traverse the given nums, whether current subsequence is a valid depends on whether previous subsequence is valid. So, there must be lots of overlapping subproblems. | |
Let's define subproblems dp[i]: length of increasing subsequence end with ith element | |
So, our goal is return max(dp[0], dp[1],.., dp[n-1]) instead of dp[n-1] | |
base case, i == 0 | |
dp[0] = 1 | |
if cuurent subproblems relies on all previoust subproblems. | |
if nums[i] > nums[j]: | |
dp[i] = max(dp[i], dp[j] + 1) | |
u don't know which subproblem dp[j] will contribute dp[i] the max lengh of increasing subsequence | |
so you take maximum | |
[1,2,3,4,5] | |
i | |
j | |
i | |
j j | |
Note: | |
1. To current subproblems i, every previous subrproblem dp[j] are already solved. | |
""" | |
def lengthOfLIS(self, nums: List[int]) -> int: | |
""" | |
Don't forget to simply describe brute force solution orally during the interview | |
before getting started to use any algorithm technique. | |
Brute Force: | |
The simplest approach is to try to find all increasing subsequences and then returning the maximum length of longest increasing subsequence. | |
And, the time complexity is (2**n). | |
However, it's inefficient, and we found the main problem could be divided into overlapping supproblem. So, we use DP. | |
Note: | |
1. Each cell in dp represent longest length of increasing subsequence considering the current element | |
2. dp[i]= represents length of LIS including nums[j]. | |
T: O(n**2) because of two loops of n there | |
S: O(n) because we use extra space for the memorization table. | |
""" | |
n = len(nums) | |
if n == 0: | |
return 0 | |
if n == 1: | |
return 1 | |
dp = [1 for _ in range(n)] # Step1: base case: dp[0] = 1 | |
for i in range(1, n): | |
for j in range(i): | |
# Step2: recursive formulation | |
if nums[i] > nums[j]: | |
dp[i] = max(dp[j]+1, dp[i]) | |
return max(dp) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment