Google Dynamic Programming Leetcode Study Guide

def trap(height: list[int]) -> int:
    """
    Returns the amount of rain water that can be trapped.

    Args:
    height (list[int]): A list of non-negative integers representing the height of each bar.

    Returns:
    int: The amount of rain water that can be trapped.
    """
    if not height:
        return 0

    # Initialize two pointers
    left, right = 0, len(height) - 1
    max_left, max_right = height[left], height[right]
    result = 0

    while left < right:
        max_left = max(max_left, height[left])
        max_right = max(max_right, height[right])

        if max_left < max_right:
            result += max_left - height[left]
            left += 1
        else:
            result += max_right - height[right]
            right -= 1

    return result

def minCost(n: int, cuts: list[int]) -> int:
    """
    Returns the minimum cost to make all the cuts.

    Args:
    n (int): The length of the stick.
    cuts (list[int]): A list of cuts.

    Returns:
    int: The minimum cost to make all the cuts.
    """
    cuts.sort()
    cuts = [0] + cuts + [n]

    dp = [[0] * len(cuts) for _ in range(len(cuts))]

    for length in range(2, len(cuts)):
        for left in range(len(cuts) - length):
            right = left + length
            dp[left][right] = float('inf')
            for i in range(left + 1, right):
                dp[left][right] = min(dp[left][right], dp[left][i] + dp[i][right] + (cuts[right] - cuts[left]) * (cuts[i] - cuts[left]))

    return dp[0][len(cuts) - 1]

def isMatch(s: str, p: str) -> bool:
    """
    Returns whether the input string matches the pattern.

    Args:
    s (str): The input string.
    p (str): The pattern.

    Returns:
    bool: Whether the input string matches the pattern.
    """
    dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
    dp[-1][-1] = True

    for i in range(len(s), -1, -1):
        for j in range(len(p) - 1, -1, -1):
            match = i < len(s) and (p[j] == s[i] or p[j] == '.')
            if j + 1 < len(p) and p[j + 1] == '*':
                dp[i][j] = dp[i][j + 2] or match and dp[i + 1][j]
            else:
                dp[i][j] = match and dp[i + 1][j + 1]

    return dp[0][0]

def isMatch(s: str, p: str) -> bool:
    """
    Returns whether the input string matches the pattern.

    Args:
    s (str): The input string.
    p (str): The pattern.

    Returns:
    bool: Whether the input string matches the pattern.
    """
    dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
    dp[0][0] = True

    for j in range(1, len(p) + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 1]

    for i in range(1, len(s) + 1):
        for j in range(1, len(p) + 1):
            match = p[j - 1] == s[i - 1] or p[j - 1] == '?'
            if p[j - 1] == '*':
                dp[i][j] = dp[i][j - 1] or match and dp[i - 1][j]
            else:
                dp[i][j] = match and dp[i - 1][j - 1]

    return dp[len(s)][len(p)]

def canJump(nums: list[int]) -> bool:
    """
    Returns whether we can reach the last index.

    Args:
    nums (list[int]): A list of non-negative integers.

    Returns:
    bool: Whether we can reach the last index.
    """
    last_pos = len(nums) - 1
    for i in range(len(nums) - 1, -1, -1):
        if i + nums[i] >= last_pos:
            last_pos = i

    return last_pos == 0

def uniquePathsWithObstacles(obstacleGrid: list[list[int]]) -> int:
    """
    Returns the number of unique paths.

    Args:
    obstacleGrid (list[list[int]]): A 2D list representing the grid.

    Returns:
    int: The number of unique paths.
    """
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [[0] * n for _ in range(m)]

    for i in range(m):
        for j in range(n):
            if obstacleGrid[i][j] == 0:
                if i == 0 and j == 0:
                    dp[i][j] = 1
                elif i == 0:
                    dp[i][j] = dp[i][j - 1]
                elif j == 0:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    return dp[-1][-1]

def minPathSum(grid: list[list[int]]) -> int:
    """
    Returns the minimum path sum.

    Args:
    grid (list[list[int]]): A 2D list representing the grid.

    Returns:
    int: The minimum path sum.
    """
    m, n = len(grid), len(grid[0])

    for i in range(1, n):
        grid[0][i] += grid[0][i - 1]

    for i in range(1, m):
        grid[i][0] += grid[i - 1][0]

    for i in range(1, m):
        for j in range(1, n):
            grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])

    return grid[-1][-1]

def minDistance(word1: str, word2: str) -> int:
    """
    Returns the minimum edit distance.

    Args:
    word1 (str): The first word.
    word2 (str): The second word.

    Returns:
    int: The minimum edit distance.
    """
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i

    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

    return dp[m][n]

def maximalRectangle(matrix: list[list[str]]) -> int:
    """
    Returns the area of the maximal rectangle.

    Args:
    matrix (list[list[str]]): A 2D binary matrix.

    Returns:
    int: The area of the maximal rectangle.
    """
    if not matrix:
        return 0

    n = len(matrix[0])
    height = [0] * (n + 1)
    result = 0

    for row in matrix:
        for i in range(n):
            height[i] = height[i] + 1 if row[i] == '1' else 0

        stack = [-1]
        for i in range(n + 1):
            while height[i] < height[stack[-1]]:
                h = height[stack.pop()]
                w = i - 1 - stack[-1]
                result = max(result, h * w)
            stack.append(i)

    return result

def generate(numRows: int) -> list[list[int]]:
    """
    Returns the first numRows of Pascal's triangle.

    Args:
    numRows (int): The number of rows.

    Returns:
    list[list[int]]: The first numRows of Pascal's triangle.
    """
    triangle = [[1] * (i + 1) for i in range(numRows)]
    for i in range(2, numRows):
        for j in range(1, i):
            triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j]

    return triangle

def minimumTotal(triangle: list[list[int]]) -> int:
    """
    Returns the minimum path sum.

    Args:
    triangle (list[list[int]]): A triangle.

    Returns:
    int: The minimum path sum.
    """
    n = len(triangle)
    dp = [[0] * len(row) for row in triangle]

    dp[0][0] = triangle[0][0]

    for i in range(1, n):
        dp[i][0] = dp[i - 1][0] + triangle[i][0]
        dp[i][-1] = dp[i - 1][-1] + triangle[i][-1]

        for j in range(1, len(triangle[i]) - 1):
            dp[i][j] = triangle[i][j] + min(dp[i - 1][j - 1], dp[i - 1][j])

    return min(dp[-1])

def maxProfit(prices: list[int]) -> int:
    """
    Returns the maximum profit.

    Args:
    prices (list[int]): A list of prices.

    Returns:
    int: The maximum profit.
    """
    result = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            result += prices[i] - prices[i - 1]

    return result

def maxProfit(prices: list[int]) -> int:
    """
    Returns the maximum profit.

    Args:
    prices (list[int]): A list of prices.

    Returns:
    int: The maximum profit.
    """
    buy1, buy2 = float('-inf'), float('-inf')
    sell1, sell2 = 0, 0

    for price in prices:
        buy1 = max(buy1, -price)
        sell1 = max(sell1, buy1 + price)
        buy2 = max(buy2, sell1 - price)
        sell2 = max(sell2, buy2 + price)

    return sell2

def partition(s: str) -> list[list[str]]:
    """
    Returns all possible palindrome partitions.

    Args:
    s (str): The input string.

    Returns:
    list[list[str]]: All possible palindrome partitions.
    """
    def is_palindrome(s: str) -> bool:
        return s == s[::-1]

    def backtrack(start: int, path: list[str]):
        if start == len(s):
            result.append(path[:])
            return

        for end in range(start, len(s)):
            if is_palindrome(s[start:end + 1]):
                path.append(s[start:end + 1])
                backtrack(end + 1, path)
                path.pop()

    result = []
    backtrack(0, [])
    return result

def maxProduct(nums: list[int]) -> int:
    """
    Returns the maximum product.

    Args:
    nums (list[int]): A list of integers.

    Returns:
    int: The maximum product.
    """
    max_product = min_product = result = nums[0]

    for i in range(1, len(nums)):
        if nums[i] < 0:
            max_product, min_product = min_product, max_product

        max_product = max(nums[i], max_product * nums[i])
        min_product = min(nums[i], min_product * nums[i])

        result = max(result, max_product)

    return result

def maxProfit(k: int, prices: list[int]) -> int:
    """
    Returns the maximum profit.

    Args:
    k (int): The maximum number of transactions.
    prices (list[int]): A list of prices.

    Returns:
    int: The maximum profit.
    """
    if k >= len(prices) // 2:
        return sum(max(0, b - a) for a, b in zip(prices, prices[1:]))

    dp = [[0] * len(prices) for _ in range(k + 1)]

    for i in range(1, k + 1):
        max_diff = -prices[0]
        for j in range(1, len(prices)):
            dp[i][j] = max(dp[i][j - 1], prices[j] + max_diff)
            max_diff = max(max_diff, dp[i - 1][j] - prices[j])

    return dp[k][-1]

def maximalSquare(matrix: list[list[str]]) -> int:
    """
    Returns the side length of the maximal square.

    Args:
    matrix (list[list[str]]): A 2D binary matrix.

    Returns:
    int: The side length of the maximal square.
    """
    if not matrix:
        return 0

    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    result = 0

    for i in range(m):
        for j in range(n):
            if matrix[i][j] == '1':
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                result = max(result, dp[i][j])

    return result * result

def nthUglyNumber(n: int) -> int:
    """
    Returns the nth ugly number.

    Args:
    n (int): The index.

    Returns:
    int: The nth ugly number.
    """
    ugly = [1]
    i2, i3, i5 = 0, 0, 0

    while len(ugly) < n:
        next_ugly = min(ugly[i2] * 2, ugly[i3] * 3, ugly[i5] * 5)
        ugly.append(next_ugly)

        if next_ugly == ugly[i2] * 2:
            i2 += 1
        if next_ugly == ugly[i3] * 3:
            i3 += 1
        if next_ugly == ugly[i5] * 5:
            i5 += 1

    return ugly[-1]

def numSquares(n: int) -> int:
    """
    Returns the least number of perfect square numbers.

    Args:
    n (int): The input number.

    Returns:
    int: The least number of perfect square numbers.
    """
    dp = [float('inf')] * (n + 1)
    dp[0] = 0

    for i in range(1, n + 1):
        j = 1
        while j * j <= i:
            dp[i] = min(dp[i], dp[i - j * j] + 1)
            j += 1

    return dp[n]

def lengthOfLIS(nums: list[int]) -> int:
    """
    Returns the length of the longest increasing subsequence.

    Args:
    nums (list[int]): A list of integers.

    Returns:
    int: The length of the longest increasing subsequence.
    """
    if not nums:
        return 0

    dp = [1] * len(nums)

    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

def maxCoins(balloons: list[int]) -> int:
    """
    Returns the maximum coins.

    Args:
    balloons (list[int]): A list of integers.

    Returns:
    int: The maximum coins.
    """
    balloons = [1] + [x for x in balloons] + [1]

    dp = [[0] * len(balloons) for _ in range(len(balloons))]

    for length in range(2, len(balloons)):
        for left in range(len(balloons) - length):
            right = left + length
            for i in range(left + 1, right):
                dp[left][right] = max(dp[left][right], balloons[left] * balloons[i] * balloons[right] + dp[left][i] + dp[i][right])

    return dp[0][len(balloons) - 1]

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        """
        Returns the maximum amount.

        Args:
        root (Optional[TreeNode]): The root of the tree.

        Returns:
        int: The maximum amount.
        """
        def dfs(node):
            if not node:
                return 0, 0

            left_no_rob, left_rob = dfs(node.left)
            right_no_rob, right_rob = dfs(node.right)

            no_rob = max(left_no_rob, left_rob) + max(right_no_rob, right_rob)
            rob = node.val + left_no_rob + right_no_rob

            return no_rob, rob

        return max(dfs(root))