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?

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]

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

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])

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])

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]

"""
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.

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

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

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]