# General

## Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

```java
public int climbStairs(int n) {
    if (n == 0 || n == 1) return n;
    int[] f = new int[n+1];
    f[0] = 1;
    f[1] = 1;
    for (int i=2; i<=n; i++){
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}
```

## Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it.

* Func: f\[i] = f\[i-1]\(if s\[i-1]!='0')+f\[i-2]\(if(s\[i-2]s\[i-1] == '10'-'26'))
* Init f\[0]=f\[1]=1
* Ans f\[n]

```python
def numDecodings(self, s: str) -> int:       
    dp = [0] * (len(s)+1)
    
    dp[0] = 1
    dp[1] = 1 if s[0] != '0' else 0
    
    for i in range(2, len(s)+1):
        if s[i-1] != '0':
            dp[i] = dp[i-1]
        if 10 <= int(s[i-2:i]) <= 26:
            dp[i] += dp[i-2]
    
    return dp[len(s)]
```

## 300 Longest Increasing Subsequence

Given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

Example For \[5, 4, 1, 2, 3], the LIS is \[1, 2, 3], return 3 For \[4, 2, 4, 5, 3, 7], the LIS is \[2, 4, 5, 7], return 4

* Brute Time O(2^n)
* State: f\[i] = LIS in index i
* Init: f\[0...i] = 1
* function: f\[i] = max{f\[j]+1}, j\<i && num\[j]\<num\[i]
* Ans: max{f\[0...i]}
* Time O(n^2), Space O(n)
* Compare to [Longest Consecutive Sequence](../array/general)

```java
public int longestIncreasingSubsequence(int[] nums) {
    int[] f = new int[nums.length];

    int ans = 0;
    for (int i=1; i<nums.length; i++){
        f[i] = 1; // init
        for(int j=0; j<i; j++){
                                 // 1 is f[j] itself
            if(nums[j] < nums[i] && f[j]+1 > f[i]){
                f[i] = f[j] + 1;
            }
        }
        ans = Math.max(ans, f[i]);
    }
    return ans;
}
```

## 53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

* dp\[i]: in nums\[0:i], the maximum subarray containing nums\[i]
* dp\[i] = max(dp\[i-1]+nums\[i], nums\[i])

```java
public int maxSubArray(int[] nums) {
    int maxSum = nums[0];
    int ans = nums[0];

    for(int i=1; i<nums.length; i++){
        maxSum = Math.max(maxSum+nums[i], nums[i]);
        ans = Math.max(ans, maxSum);
    }
    return ans;
}
```

## 152. Maximum Product Subarray

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

* max\[i]: in nums\[0:i], the maximum product subarray containing nums\[i]
* Maintain a min and a max variable, if nums\[i] is negative, swap them
* ans\[i] = max(max\[i-1]+nums\[i], nums\[i])

```java
public int maxProduct(int[] nums) {
    int ans=nums[0], min=nums[0], max=nums[0];
    for(int i=1; i<nums.length; i++){
        if(nums[i] < 0){
            int tmp = min;
            min = max;
            max = tmp;
        } 
        // if nums[i]==0, both max and min will be updated as 0, so disrupt the continuous
        max = Math.max(nums[i], max*nums[i]);
        min = Math.min(nums[i], min*nums[i]);
        ans = Math.max(ans, max);
    }
    return ans;
}
```

\
96\. Unique Binary Search Tree
------------------------------

Given _n_, how many structurally unique **BST's** (binary search trees) that store values 1 ... _n_?

`[1, 2, 3, 4, 5, 6, 7]` with `3` as the root, left subsequence `[1, 2]` and the right subsequence `[4, 5, 6, 7],` dp\[2] \* dp\[4] to dp\[7]

```python
"""
dp[i] 為數字 i 所以可構成的BST個數
dp[i] = sum of dp[j-1] * dp[i-j] for 1 <= j <= i
"""
class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n+1)
        dp[0], dp[1] = 1, 1
        
        for i in range(2, n+1):
            for j in range(1, i+1):
                dp[i] += dp[j-1] * dp[i-j]
                
        return dp[n]
```

## 95. Unique Binary Search Tree II

Given an integer _n_, generate all structurally unique **BST's** (binary search trees) that store values 1 ... _n_.

```python
def generateTrees(self, n: int) -> List[TreeNode]:
    if not n: return []
    return self.helper(1, n)

def helper(self, start, end):
    if start > end:
        return [None]
    
    if start == end:
        return [TreeNode(start)]
    
    res = []
    
    for i in range(start, end+1):
        lefts = self.helper(start, i-1)
        rights = self.helper(i+1, end)
        
        for l in lefts:
            for r in rights:
                node = TreeNode(i)
                node.left = l
                node.right = r
                res.append(node)
    return res
```

## 1235. Maximum Profit in Job Scheduling&#x20;

We have `n` jobs, where every job is scheduled to be done from `startTime[i]` to `endTime[i]`, obtaining a profit of `profit[i]`.

* DP + binary search

```python
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
    # sort by end, 如果sort by start, 有可能其中一個period 很長
    # 而這個period 中間如果有更高的profit 就會搜尋不到
    jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
    
    # base case
    dp = [[0, 0]]
    
    for s, e, p in jobs: 
                                # start day+1 作為upper bound
        idx = bisect.bisect(dp, [s+1])-1
        
        # 如果每一次都update
        # corner case: 有重複的start and end 的時候, 不一定拿到較大profit那個
        if dp[idx][1] + p > dp[-1][1]:
            dp.append([e, dp[idx][1]+p])
    return dp[-1][1]
```
