[LeetCode] 1162. As Far from Land as Possible

 Problem : https://leetcode.com/problems/as-far-from-land-as-possible/description/

Start from all the land cells and use BFS approach to calculate Manhattan distance for each water cells.

Manhattan distance means on each step, we can move to the 4 conjunctive cells ( up, down, left, right ).

Because of memorization, each cell will only be visited once.

Time complexity : O ( M * N ), M = len(grid), N = len(grid[0])

class Solution {
    static final int[][] diffs = new int[][] { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

    public int maxDistance(int[][] grid) {
        int ROW = grid.length;
        int COLUMN = grid[0].length;

        int[][] memo = new int[ROW][COLUMN];
        Deque<int[]> queue = new LinkedList<>();

        for (int y = 0; y < ROW; y++) {
            for (int x = 0; x < COLUMN; x++) {
                if (grid[y][x] == 1)
                     queue.offerLast(new int[] {y, x});
            }
        }

        int result = -1;
        int step = 1;
        
        while (!queue.isEmpty()) {
            int n = queue.size();

            for (int i = 0; i < n; i++) {
                int[] cur = queue.pollFirst();
                int cy = cur[0], cx = cur[1];

                for (int[] d : diffs) {
                    int ny = cy + d[0], nx = cx + d[1];

                    if (0 <= ny && ny < ROW && 
                        0 <= nx && nx < COLUMN && 
                        grid[ny][nx] == 0 && 
                        (memo[ny][nx] == 0 || memo[ny][nx] > step)) {
                        memo[ny][nx] = step;
                        queue.offerLast(new int[] {ny, nx});
                    }
                }
            }

            if (!queue.isEmpty()) {
                result = Math.max(result, step);
            }
            
            step += 1;
        }


        return result;
    }
}

[LeetCode] 1463. Cherry Pickup II

 Problem : https://leetcode.com/problems/cherry-pickup-ii/

The final result only depends on the track of robot 1 and robot 2. The order of robot movement won't affect the final result. But if we move the 2 robots separately, the optimal track of one robot depends on the other robot's track. We will need to record the whole track of one robot to get the optimal track of another robot.

If we move the 2 robots synchronously, the optimal result only depends on the new position of the 2 robots on the next row.

class Solution {
    int ROW;
    int COLUMN;
    
    int[][] grid;
    int[][][] memo;
    
    int[] diff = new int[] {-1, 0, 1};
    
    public int cherryPickup(int[][] grid) {
        this.ROW = grid.length;
        this.COLUMN = grid[0].length;
        this.grid = grid;
        this.memo = new int[ROW][COLUMN][COLUMN];
        
        return helper(0, 0, COLUMN-1);
    }
    
    int helper(int y, int x1, int x2) {
        if (y >= ROW || x1 < 0 || x1 >= COLUMN || x2 < 0 || x2 >= COLUMN) {
            return 0;
        }
        
        if (memo[y][x1][x2] != 0) {
            return memo[y][x1][x2];
        }
        
        int result = x1 != x2 ? grid[y][x1] + grid[y][x2] : grid[y][x1];
        
        int tmp = 0;
        
        for (int dx1 : diff) {
            for (int dx2: diff) {
                tmp = Math.max(tmp, helper(y+1, x1 + dx1, x2 + dx2));
            } 
        }
        
        memo[y][x1][x2] = result + tmp;
        return memo[y][x1][x2];
    }
}

[LeetCode] 717. 1-bit and 2-bit Characters

 Problem : https://leetcode.com/problems/1-bit-and-2-bit-characters/

Remove the last 2 bits, then check if the remaining sequence is still valid.

If the remaining sequence is not valid, then the last character must be a one-bit character.

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        
        @cache
        def helper(i):
            """
            return True is bits[:i] is a valid sequence
            """
            
            if i == 0:
                return True
            
            # bits[i-1] can be decoded as the one-bit character
            if bits[i-1] == 0 and helper(i-1):
                return True
            
            # bits[i-2]bits[i-1] can be decoded as the two-bit character
            if i - 2 >= 0 and bits[i-2] == 1:
                return helper(i-2)
            
            # bits[:i] is an invalid sequence
            return False
        
        # bits[-2] == 0 so bits[-1] must be decoded as one-bit character
        if len(bits) == 1 or bits[-2] == 0: return True
        
        # return False if the remaining sequence is still valid by removing the last 2 bits
        return not helper(len(bits) - 2)

[LeetCode] 639. Decode Ways II

 Problem : https://leetcode.com/problems/decode-ways-ii/

The top-down solution:

class Solution:
    def numDecodings(self, s: str) -> int:
        
        @cache
        def helper(start):
            """
            total decoding way of s[start:]
            """
            
            if start == len(s):
                return 1
            
            # '0' cannot be the leading digit
            if s[start] == '0':
                return 0
            
            # total decoding way when consider s[start] is a letter
            result = (9 if s[start] == '*' else 1) * helper(start + 1)
            
            # total decoding way when consider s[start]s[start+1] is a letter 
            if start + 1 < len(s):
                if s[start] == '1':
                    if s[start+1] != '*':
                        result += 1 * helper(start + 2)
                    else:
                        # s[start+1] == '*'
                        result += 9 * helper(start + 2)
                elif s[start] == '2':
                    if '0' <= s[start+1] <= '6':
                        result += 1 * helper(start + 2)
                    elif s[start+1] == '*':
                        result += 6 * helper(start + 2)
                elif s[start] == '*':
                    if '0' <= s[start+1] <= '6':
                        result += 2 * helper(start + 2)
                    elif '7' <= s[start+1] <= '9':
                        result += 1 * helper(start + 2)
                    elif s[start+1] == '*':
                        result += (9 + 6) * helper(start+2)
            
            return result % (10 ** 9 + 7)
         
        return helper(0)

The bottom-up solution:

class Solution:
    def numDecodings(self, s: str) -> int:
        M = 10 ** 9 + 7
        N = len(s)
        
        if s[0] == '0': return 0
        
        dp = [0] * (N+1)
        dp[0] = 1
        dp[1] = 9 if s[0] == '*' else 1
        
        for i in range(1, N):
            if s[i] == '*':
                dp[i+1] = 9 * dp[i] % M
                
                if s[i-1] == '1':
                    dp[i+1] = (dp[i+1] + 9 * dp[i-1]) % M
                elif s[i-1] == '2':
                    dp[i+1] = (dp[i+1] + 6 * dp[i-1]) % M
                elif s[i-1] == '*':
                    dp[i+1] = (dp[i+1] + 15 * dp[i-1]) % M
            else:
                dp[i+1] = dp[i] if s[i] != '0' else 0
                if s[i-1] == '1':
                    dp[i+1] = (dp[i+1] + dp[i-1]) % M
                elif s[i-1] == '2' and s[i] <= '6':
                    dp[i+1] = (dp[i+1] + dp[i-1]) % M
                elif s[i-1] == '*':
                    if s[i] <= '6':
                        dp[i+1] = (dp[i+1] + 2 * dp[i-1]) % M
                    else:
                        dp[i+1] = (dp[i+1] + dp[i-1]) % M
        
        return dp[N]

[LeetCode] 464. Can I Win

 Problem : https://leetcode.com/problems/can-i-win/

The state of this game is the integers be used. Because maximal number of integer is no more than 20.  

We can use bitmask to remember the used integers. 

Also use True to represent the first player wins and use False to represent the second player wins.

Time complexity = O( 2 ** N ).   For each integer we consider whether use it or not to form a new state.  There are 2 ** N states. 

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        
        # use bitmask to remember the picked integer
        mask = 0
        
        @cache
        def helper(mask, sums, a):
            for i in range(maxChoosableInteger):
                
                # bypass if the integer (i+1) is already used
                if mask & (1 << i) != 0:
                    continue
                
                # current player wins when sums >= desiredTotal
                if sums + i + 1 >= desiredTotal:
                    return a
                
                # mark integer (i+1) is used
                mask ^= (1 << i)
                
                # because both players play optimally
                # we consider current player must chooses this routine
                # which leads to a win result for hime
                if helper(mask, sums + i + 1, not a) ==  a:
                    
                    # mark integer (i+1) is not used
                    mask ^= (1 << i)
                    
                    # current player can force a win
                    return a
                
                # mark integer (i+1) is not used
                mask ^= (1 << i)
            
            # current player cannot force a win
            return not a
        
        # it is impossible to win whe sum of all integers is less than the desiredTotal
        if maxChoosableInteger * (maxChoosableInteger + 1) // 2 < desiredTotal: return False
        
        return helper(0, 0, True)

[LeetCode] 377. Combination Sum IV

 Problem : https://leetcode.com/problems/combination-sum-iv/

This quiz is similar to "Coin Change". 

Assume taking nums[i], find the combination for sum = target - nums[i].

Time complexity = O ( M * N ). M = target, N = len(nums)

Top-down solution:

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        N = len(nums)
        nums.sort()
        
        @lru_cache(maxsize = None)
        def helper(remain):
            if remain == 0: return 1
            
            result = 0
            
            for i in range(N):
                if nums[i] <= remain:
                    result += helper(remain - nums[i])
                else:
                    break
            
            return result

        return helper(target)

Bottom-up solution:

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        
        nums.sort()
        
        for combo in range(1, target+1):
            for n in nums:
                if n > combo:
                    break
                    
                dp[combo] += dp[combo - n]
        
        return dp[target]

Follow-up question:

To allow negative number in the given array, we need to limit the ouput combination length. Otherwise, it won't be able to stop the searching.

[LeetCode] 343. Integer Break

 Problem : https://leetcode.com/problems/integer-break/

For each number i,  it can be broken into at least  j,  (i-j).  j = [1 ... i -1]

Let DP[i] = maximum product of number i when i be broken into at least 2 integers.

DP[i] = Max( j * (i-j),  j * DP[i-j] ),    j = [ 1 ... i - 1 ]

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [1] * (n+1)
        
        for i in range(3, n+1):
            for j in range(1, i):
                dp[i] = max(dp[i], max(j* (i-j),  j *dp[i-j]))
        
        return dp[n]

Another memorization approach:

class Solution {
    int[] memo;
    
    public int integerBreak(int n) {
        memo = new int[n+1];
        memo[1] = 1;
        
        return helper(n);
    }
    
    int helper(int n) {
        if (memo[n] != 0) {
            return memo[n];
        }
        
        for (int x = 1; x <= n / 2; x++) {
            
            // i.e. For number 3,  helper(3) = 1 * 2 = 2. 
            // 3 > helper(3).  we need to use 3 instead of helper(3) to get the larger product.
            memo[n] = Math.max(memo[n], Math.max(x, helper(x)) * Math.max(n-x, helper(n-x)));
        } 
        
        return memo[n];
    }
}

Edited on 11/26/2021. Update the top-down solution.

[LeetCode] 337. House Robber III

 Problem : https://leetcode.com/problems/house-robber-iii/

Each level of the tree has 2 state :   safe or  not-safe.

If current level is safe to rob, thief can choose rob current level then next level is not safe to rob. Or skip current level, then next level is safe to rob.

Use memorization approach to find the answer.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rob(self, root: TreeNode) -> int:
        
        @lru_cache(maxsize = None)
        def helper(node, safe):
            result = 0
            
            if node:
                if safe:
                    result = node.val + helper(node.left, not safe) + helper(node.right, not safe)
                    result = max(result, helper(node.left, safe) + helper(node.right, safe))
                else:
                    result = helper(node.left, not safe) + helper(node.right, not safe)
                
            return result
        
        return max(helper(root, True), helper(root, False))

[LeetCode] 329. Longest Increasing Path in a Matrix

 Problem : https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        ROW = len(matrix)
        COLUMN = len(matrix[0])
        
        diff = ((0,1), (0,-1), (1,0), (-1,0))
        
        @cache
        def helper(y, x):
            """
            Longest increasing path starts from matrix[y][x]
            """
            result = 1
            for dx, dy in diff:
                nx = x + dx
                ny = y + dy
                if 0 <= nx < COLUMN and 0 <= ny < ROW and matrix[y][x] < matrix[ny][nx]:
                    # increasing sequence can only be built with one direction
                    # no need to mark the visited positions
                    result = max(result, 1 + helper(ny, nx))
            
            return result
        
        result = 1
        for y in range(ROW):
            for x in range(COLUMN):
                result = max(result, helper(y,x))
        return result

Edited on 04/10/2021. Use @cache annotation.

[LeetCode] 322. Coin Change

Problem : https://leetcode.com/problems/coin-change/

Time Complexity = O ( M * N ),   M = amount,  N = len(coins).

Top-down Solution :

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        
        MAX_INT = 2 ** 31 - 1
        N = len(coins)
        coins.sort()
        
        @lru_cache(maxsize = None)
        def helper(amount):
            """
            Fewest number of coins needed
            to make up this amount.
            """
            if amount == 0:
                return 0
            
            result = MAX_INT
            
            for i in range(N):
                if coins[i] > amount:
                    break
                
                tmp = helper(amount - coins[i])
                if tmp != -1:
                    result = min(result, tmp + 1)
            
            return result if result != MAX_INT else -1
        
        
        return helper(amount)

Bottom-up Solution:

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # dp[n] = Fewest number of coins needed to make up amount n
        dp = [amount+1] * (amount + 1)
        dp[0] = 0
        
        coins.sort()
        
        for n in range(1, amount+1):
            for coin in coins:
                if coin > n:
                    break
                
                dp[n] = min(dp[n], dp[n-coin] + 1)
        
        return dp[-1] if dp[-1] != amount + 1 else -1

[LeetCode] 312. Burst Ballons

 Problem : https://leetcode.com/problems/burst-balloons/

Time Complexity = O ( N ** 3 ) 

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]
        
        @lru_cache(maxsize = None)
        def dp(left, right):
            """
            maximumal coins can get for section section(left : right)
            left and right is excluded from this section
            """
            
            if left + 1 == right:
                # not include left and right
                return 0
            
            result = 0
            for i in range(left+1, right):
                # Balllon list = nums[left] , section(left, i), nums[i], section(i, right), nums[right]
                # tmpResult = nums[left] * nums[i] * nums[right] + max coins of section(left,i) + max coins of section(i, right)
                tmp = nums[left] * nums[i] * nums[right]
                tmp += dp(left, i)
                tmp += dp(i, right)
                result = max(result,  tmp)
            
            return result
        
        
        return dp(0, len(nums) - 1)

[LeetCode] 309. Best Time to Buy and Sell Stock with Cooldown

 Problem : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

Each day has either 3 state :  Buy, Sell, CoolDown

On day i:

If it is in "buy" state, then it either buy stock on the last day, or it buy stock on day i ( cool down on last day ) .

If it is in "sell" state, then it either sell stock on the last day, or it sell stock on day i.

If it is in "cooldown" state, then it either cool down on last day, or it sell stock on last day.

Helper(i, state) returns the maximum profit on day i  in  x state.

To get the maximum profit on the last day,  it returns the profit can be made on the last day in "sell" state.

Top-Down Solution:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy, sell, cooldown = 0, 1, 2
        
        @lru_cache(maxsize = None)
        def helper(i, state):
            if i < 0:
                return 0
            
            if i == 0 and state == sell:  
                return 0
            
            if i == 0 and state == buy:
                return -1 * prices[0]
            
            if i == 0 and state == cooldown:
                return 0
            
            if state == buy:
                # max(buy-on-last-day,  buy-on-day-i)
                return max(helper(i-1, buy), -1 * prices[i] + helper(i-1, cooldown))
            
            if state == sell:
                # max(sell-on-last-day, sell-on-day-i)
                return max(helper(i-1, sell), prices[i] + helper(i-1, buy))
            
            if state == cooldown:
                # max(continue-cool-down, sell-on-last-day)
                return max(helper(i-1, cooldown), helper(i-1, sell)
    
        return helper(len(prices)-1, sell)

Bottom-Up Solution:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        if not prices:
            return 0
        
        buy = [0] * len(prices)
        sell = [0] * len(prices)
        cooldown = [0] * len(prices)
        
        buy[0] = -prices[0]
        
        for i in range(1, len(prices)):
            buy[i] = max(buy[i-1], -1 * prices[i] + cooldown[i-1])
            sell[i] = max(sell[i-1], buy[i-1] + prices[i])
            cooldown[i] = max(cooldown[i-1], sell[i-1]) 
            
        return sell[-1]

[LeetCode] 279. Perfect Squares

 Problem : https://leetcode.com/problems/perfect-squares/

I know there is a much better solution. But this memorization approach is easy to understand for me.

class Solution {
    HashMap<Integer, Integer> memo = new HashMap();
    
    {
        memo.put(0, 0);
    }
    
    public int numSquares(int n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        int result = Integer.MAX_VALUE;
        
        for (int x = 1; x * x <= n; x++) {   
            result = Math.min(result, 1 + numSquares(n - x*x));
        } 
        
        memo.put(n, result);
        return result;
    }
}

A buttom-up solution:

class Solution:
    def numSquares(self, n: int) -> int:
        INT_MAX = 2**31 - 1
        
        dp = [INT_MAX] * (n+1)
        dp[0] = 0
        
        i = 1
        while i * i < n:
            dp[i*i] = 1
            i += 1
        
        for i in range(1, n+1):
            if dp[i] != INT_MAX: continue
                
            for j in range(1, int(math.sqrt(i)) + 1):
                dp[i] = min(dp[i], dp[i - j*j] + 1)
        
        return dp[n]

Edited on 12/02/2021. Update the top-down solution.

[LeetCode] 213. House Robber II

 Problem : https://leetcode.com/problems/house-robber-ii/

Since the first and the last house are exclusive to each other. 

We can break it into 2 cases:

- Start from the first house and end at the 2nd from the last house.

- Start from the 2nd house and end at the last house.

The answer is the max value of the 2 cases.

class Solution:
    def rob(self, nums: List[int]) -> int:
        
        @lru_cache(maxsize = None)
        def helper(i, end, safe):
            """
            i : current house
            end: last house index
            safe: safe to rob
            """
            if i == end:
                return 0
            
            stolen = 0
            
            if safe:
                stolen = max(nums[i] + helper(i+1, end, False), helper(i+1, end, True))
            else:
                stolen = helper(i+1, end, True)
            
            return stolen
        
        if not nums:
            return 0
        
        if len(nums) < 2:
            return max(nums)
        
        return max(helper(0, len(nums) - 1, True), helper(1, len(nums), True))

Bottom-Up approach

class Solution:
    def rob(self, nums: List[int]) -> int:
        
        def helper(houses):
            steal = [0] * len(houses)
            steal[0] = houses[0]
            
            notSteal = [0] * len(houses)
            
            for i in range(1, len(houses)):
                steal[i] = notSteal[i-1] + houses[i]
                notSteal[i] = max(notSteal[i-1], steal[i-1])
          
            return max(steal[-1], notSteal[-1])
        
        if not nums:
            return 0
        
        if len(nums) == 1:
            return nums[0]
        
        if len(nums) == 2:
            return max(nums[0], nums[1])
        
        return max(helper(nums[1:]), helper(nums[:-1]))

[LeetCode] 198. House Robber

 Problem : https://leetcode.com/problems/house-robber/

Robber has 2 choices for each house,  steal this house if the previous house is not be stolen or not steal this house.

DP solution

Time Complexity = O ( N )

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        if len(nums) <= 2:
            return max(nums)
        
        steal = [0] * len(nums)
        notSteal = [0] * len(nums)
        
        steal[0] = nums[0]
       
        for i in range(1, len(nums)):
            steal[i] = notSteal[i-1] + nums[i]
            notSteal[i] = max(notSteal[i-1], steal[i-1])
            
        return max(steal[-1], notSteal[-1])

Another DP solution

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        if len(nums) <= 2:
            return max(nums)
        
        dp = [0] * len(nums)
        
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        
        for i in range(2, len(nums)):
            # max(not-rob-house-i, rob-house-i)
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        
        return dp[-1]

Memorization solution

Time Complexity =  O ( N ).  

class Solution:
    def rob(self, nums: List[int]) -> int:
        
        @lru_cache(maxsize = None)
        def dfs(i, safe):
            if i >= len(nums):
                return 0
            
            s1 = nums[i] + dfs(i+1, False) if safe else 0
            s2 = dfs(i+1, True)
            
            return max(s1, s2)
        
        
        return dfs(0, True)

[LeetCode] 191. Number of 1 Bits

Problem : https://leetcode.com/problems/number-of-1-bits/

An one liner solution:

Time Complexity = O(1)

class Solution:
    def hammingWeight(self, n: int) -> int:
        return sum([n >> offset & 1 for offset in range(32)])

Use bit manipulate trick to only count '1'

class Solution:
    def hammingWeight(self, n: int) -> int:
        result = 0
        while n:
            result += 1
            n = n & (n-1)
        
        return result

A divide and conquer approach. And use memorization to accelerate. ( The fastest solution. )

class Solution:
    def hammingWeight(self, n: int) -> int:
        
        #000 001 010 011 100 101 110 111
    
        @cache
        def helper(x):
            return helper(x >> 3) + helper(x & 7) if x > 7 else [0, 1, 1, 2, 1, 2, 2, 3][x]
                
        return helper(n)

Edited on 05/04/2021. Add the only count '1' solution.

Edited on 05/04/2021. Add the divide and conquer solution.

[LeetCode] 188. Best Time to Buy and Sell Stock IV

 Problem : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

On each day, it has 2 states.

1. Buy stock. ( Buy stock on current day or bought stock on previous days )

2. Sell stock. ( Sell stock on current day or sold stock on previous days )

The answer is max profit can get if sell stock on last day.

Top-Down solution:

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        buy, sell = 0, 1
        
        @lru_cache(maxsize = None)
        def dp(i, state, transaction):
            if state == buy and transaction == 0:
                # cannot buy when transaction == 0
                return -2 ** 31
            
            if state == sell and transaction == 0:
                # no profit when transaction == 0 
                return 0
            
            if i == 0 and state == buy:
                return -1 * prices[0]
            
            if i == 0 and state == sell:
                return 0
            
            if state == buy:
                # max( profit-of-buy-on-day-i [descrease transaction for selling on previous days], 
                #      profit-of-bought-on-previous-days )
                return max(-1 * prices[i] + dp(i-1, sell, transaction - 1), dp(i-1, buy, transaction))
            
            if state == sell:
                # max( profit-of-sell-on-day-i, profit-of-sold-on-previous-days )
                return max(prices[i] + dp(i-1, buy, transaction), dp(i-1, sell, transaction))
    
        if len(prices) <= 1:
            return 0
        
        # unlimited transaction when k is more than half of the amount of prices
        if k >= len(prices) // 2:
            profit = 0
            for i in range(1, len(prices)):
                if prices[i] > prices[i-1]:
                    profit += (prices[i] - prices[i-1])
                   
            return profit
        
        return dp(len(prices)-1, sell, k)

Bottom-Up solution:

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        
        if n <= 1:
            return 0
        
        # unlimited transaction when k is more than half of prices
        if k >= n  // 2:
            profit = 0
            for i in range(1, n):
                if prices[i] > prices[i-1]:
                    profit += (prices[i] - prices[i-1])
                   
            return profit
        
        # dp[n][k+1][2]
        dp = [[[0, 0] for _ in range(k+1)] for _ in range(n)] 
        
        for i in range(n):
            dp[i][0][0] = 0  # sell on day i, transaction 0 
            dp[i][0][1] = -2 ** 31 # buy on day i, transaction 0 (impossible case)
        
        for j in range(1, k+1):
            dp[0][j][0] = 0
            dp[0][j][1] = -prices[0]
        
        for i in range(1, n):
            for j in range(1, k+1):
                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])
        
        return dp[-1][-1][0]

[LeetCode] 174. Dungeon Game

Problem : https://leetcode.com/problems/dungeon-game/

Memorization Solution:

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        row = len(dungeon)
        col = len(dungeon[0])
        
        @lru_cache(maxsize = None)
        def helper(y, x):
            if y >= row or x >= col:
                return 2 ** 31 - 1
            
            if y == row -1 and x == col - 1:
                return max(1, 1 - dungeon[y][x])
            
            # only need to have 1 health point to survive 
            return max(1, min(helper(y,x+1), helper(y+1, x)) - dungeon[y][x])

        return helper(0, 0)

DP Solution:

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        row = len(dungeon)
        col = len(dungeon[0])
        
        max_int = 2 ** 31 - 1
        
        dp = [[max_int] * (col+1) for _ in range(row + 1)]
        
        dp[row][col-1] = 1
        dp[row-1][col] = 1
        
        for y in reversed(range(row)):
            for x in reversed(range(col)):
                dp[y][x] = max(1, min(dp[y+1][x], dp[y][x+1]) - dungeon[y][x])
        
        return dp[0][0]

[LeetCode] 140. Word Break II

Problem : https://leetcode.com/problems/word-break-ii/

Use memorization approach to cache the result of,  starting from position "start", whether it is possible to break string into words in dictionary.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        wordDictSet = set(wordDict)
        result = []
        
        @lru_cache(maxsize = None)
        def backtracking(start):
            if start == len(s):
                return [[]]
            
            result = []
            for i in range(start, len(s)):
                tmp = s[start:i+1]
                if tmp in wordDictSet:
                    partials = backtracking(i+1)
                    for p in partials:
                        result.append([tmp] + p)
                    
            return result
        
        result = backtracking(0)
        
        return map(lambda x : " ".join(x), result)

[LeetCode] 139. Word Break

Problem : https://leetcode.com/problems/word-break/

Iterate the input string from left to right. Find word in dictionary. If found, break the input string into 2 parts, check if the 2nd part is also constructed by the words in dictionary.

Time Complexity = O ( N )

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if not wordDict: return False
        
        wordSet = set(wordDict)
        maxLen = max([len(w) for w in wordDict])
        
        @lru_cache(maxsize=None)
        def dfs(start):
            if start >= len(s): 
                return True
            
            for i in range(start, min(start+maxLen, len(s))):
                if s[start:i+1] in wordSet and dfs(i+1):
                    return True
                    
            return False
        
        return dfs(0)

BFS solution:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if not wordDict: return False
        wordSet = set(wordDict)
        maxLen = max([len(w) for w in wordDict])
        
        queue = deque([0])
        visited = set([0])
        
        while queue:
            start = queue.popleft()
            
            for i in range(start, min(start+maxLen, len(s))):
                if s[start:i+1] in wordSet:
                    if i + 1 == len(s):
                        return True

                    if i + 1 not in visited:
                        visited.add(i+1)
                        queue.append(i+1)
        
        return False

The bottom-up solution:

class Solution {

    public boolean wordBreak(String s, List wordDict) {
        HashSet<String> words = new HashSet();
        int wordLen = 0;
            
        for (int i = 0; i < wordDict.size(); i++) {
            words.add(wordDict.get(i));
            wordLen = Math.max(wordLen, wordDict.get(i).length());
        }
        
        int N = s.length();
        boolean[] dp = new boolean[N];
        
        for (int i = N-1; i >= 0; i--) {
            for (int j = i; i - j + 1 <= wordLen && j >= 0; j--) {
                
                if (words.contains(s.substring(j, i+1)) && (i + 1 == N || dp[i+1]) ) {
                    dp[j] = true;
                }
            }
        }
        
        return dp[0];

    }
}

Edited on 11/26/2021. Add the bottom-up solution.