"""
# 309. Best Time to Buy and Sell Stock with Cooldown

## Problem
You are given an array `prices` where `prices[i]` is the price of a given stock on
the i-th day. Find the maximum profit you can achieve. You may complete as many
transactions as you like with the following restrictions:
- After you sell your stock, you cannot buy stock on the next day (cooldown of 1 day).
- You may not engage in multiple transactions simultaneously (must sell before buying).

## Examples
```text
Input:  prices = [1,2,3,0,2]
Output: 3
Explanation: Buy on day 0 (price=1), sell on day 1 (price=2),
             cooldown on day 2, buy on day 3 (price=0), sell on day 4 (price=2).
             Profit = (2-1) + (2-0) = 3

Input:  prices = [1]
Output: 0
```

## Constraints
- 1 <= prices.length <= 5000
- 0 <= prices[i] <= 1000
"""
from typing import List


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # States: holding, sold (cooldown), idle
        # holding: max(prev_holding, prev_idle - price)
        # sold: prev_holding + price
        # idle: max(prev_idle, prev_sold)
        # Time: O(n), Space: O(1)
        # States: hold (own stock), sold (just sold, next day is cooldown), rest (cooldown/idle)
        hold, sold, rest = -float('inf'), 0, 0
        for p in prices:
            hold, sold, rest = max(hold, rest - p), hold + p, max(rest, sold)
        return max(sold, rest)


if __name__ == '__main__':
    s = Solution()
    assert s.maxProfit([1,2,3,0,2]) == 3
    assert s.maxProfit([1]) == 0
    assert s.maxProfit([2,1]) == 0
    assert s.maxProfit([1,2]) == 1
    print("All tests passed.")

"""
# 312. Burst Balloons

## Problem
You are given `n` balloons, indexed from 0 to n-1. Each balloon is painted with a
number on it represented by an array `nums`. You are asked to burst all the balloons.
If you burst the i-th balloon, you will get `nums[i-1] * nums[i] * nums[i+1]` coins.
If i-1 or i+1 goes out of bounds, treat it as if there is a balloon with a 1 painted on it.
Return the maximum coins you can collect by bursting the balloons wisely.

## Examples
```text
Input:  nums = [3,1,5,8]
Output: 167
Explanation:
  Burst 1 -> 3*1*5 = 15, nums = [3,5,8]
  Burst 5 -> 3*5*8 = 120, nums = [3,8]
  Burst 3 -> 1*3*8 = 24, nums = [8]
  Burst 8 -> 1*8*1 = 8, nums = []
  Total = 15 + 120 + 24 + 8 = 167

Input:  nums = [1,5]
Output: 10
```

## Constraints
- 1 <= nums.length <= 300
- 0 <= nums[i] <= 100
"""
from typing import List


class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        # Interval DP: dp[l][r] = max coins from bursting all balloons in (l,r)
        # Try each balloon k as the LAST to burst in the interval
        # Coins from k = nums[l]*nums[k]*nums[r] + dp[l][k] + dp[k][r]
        # Time: O(n^3), Space: O(n^2)
        nums = [1] + nums + [1]
        n = len(nums)
        dp = [[0] * n for _ in range(n)]
        for length in range(2, n):
            for left in range(0, n - length):
                right = left + length
                for k in range(left + 1, right):
                    dp[left][right] = max(
                        dp[left][right],
                        nums[left] * nums[k] * nums[right] + dp[left][k] + dp[k][right]
                    )
        return dp[0][n-1]


if __name__ == '__main__':
    s = Solution()
    assert s.maxCoins([3,1,5,8]) == 167
    assert s.maxCoins([1,5]) == 10
    assert s.maxCoins([1]) == 1
    print("All tests passed.")

"""
# 518. Coin Change II

## Problem
You are given an integer array `coins` representing coins of different denominations
and an integer `amount` representing a total amount of money. Return the number of
combinations that make up that amount. If that amount cannot be made up by any
combination of the coins, return 0. You may use each coin an unlimited number of times.

## Examples
```text
Input:  amount = 5, coins = [1,2,5]
Output: 4
Explanation: 5=5, 5=2+2+1, 5=2+1+1+1, 5=1+1+1+1+1

Input:  amount = 3, coins = [2]
Output: 0

Input:  amount = 10, coins = [10]
Output: 1
```

## Constraints
- 1 <= coins.length <= 300
- 1 <= coins[i] <= 5000
- All values of coins are unique
- 0 <= amount <= 5000
"""
from typing import List


class Solution:
    def change_2d(self, amount: int, coins: List[int]) -> int:
        # Time: O(n*amount), Space: O(n*amount)
        n = len(coins)
        dp = [[0] * (amount + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            dp[i][0] = 1
        for i in range(1, n + 1):
            for j in range(1, amount + 1):
                dp[i][j] = dp[i-1][j]
                if coins[i-1] <= j:
                    dp[i][j] += dp[i][j - coins[i-1]]
        return dp[n][amount]

    def change(self, amount: int, coins: List[int]) -> int:
        # dp[i][j] = ways to make amount j using first i coins
        # Either skip coin i or use it: dp[i][j] = dp[i-1][j] + dp[i][j-coin]
        # Time: O(n*amount), Space: O(amount)
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for j in range(coin, amount + 1):
                dp[j] += dp[j - coin]
        return dp[amount]


if __name__ == '__main__':
    s = Solution()
    assert s.change(5, [1,2,5]) == 4
    assert s.change(3, [2]) == 0
    assert s.change(10, [10]) == 1
    assert s.change_2d(5, [1,2,5]) == 4
    print("All tests passed.")

"""
# 115. Distinct Subsequences

## Problem
Given two strings `s` and `t`, return the number of distinct subsequences of `s`
which equals `t`. A subsequence of a string is a new string formed from the original
string by deleting some (can be none) of the characters without disturbing the
relative positions of the remaining characters.

## Examples
```text
Input:  s = "rabbbit", t = "rabbit"
Output: 3
Explanation: Three ways to generate "rabbit" from "rabbbit":
  rabb[b]it -> rabbit (delete 3rd b)
  rab[b]bit -> rabbit (delete 2nd b)
  ra[b]bbit -> rabbit (delete 1st b)

Input:  s = "babgbag", t = "bag"
Output: 5
```

## Constraints
- 1 <= s.length, t.length <= 1000
- s and t consist of English letters
"""


class Solution:
    def numDistinct_2d(self, s: str, t: str) -> int:
        # Time: O(m*n), Space: O(m*n)
        m, n = len(s), len(t)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            dp[i][0] = 1
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                dp[i][j] = dp[i-1][j]
                if s[i-1] == t[j-1]:
                    dp[i][j] += dp[i-1][j-1]
        return dp[m][n]

    def numDistinct(self, s: str, t: str) -> int:
        # dp[i][j] = ways to form t[:j] from s[:i]
        # If s[i-1]==t[j-1]: dp[i-1][j-1] + dp[i-1][j]; else dp[i-1][j]
        # Time: O(m*n), Space: O(n)
        n = len(t)
        dp = [0] * (n + 1)
        dp[0] = 1
        for c in s:
            for j in range(n, 0, -1):
                if c == t[j-1]:
                    dp[j] += dp[j-1]
        return dp[n]


if __name__ == '__main__':
    s = Solution()
    assert s.numDistinct("rabbbit", "rabbit") == 3
    assert s.numDistinct("babgbag", "bag") == 5
    assert s.numDistinct("a", "b") == 0
    assert s.numDistinct_2d("rabbbit", "rabbit") == 3
    print("All tests passed.")

"""
# 72. Edit Distance

## Problem
Given two strings `word1` and `word2`, return the minimum number of operations
required to convert `word1` to `word2`. You have the following three operations:
- Insert a character
- Delete a character
- Replace a character

## Examples
```text
Input:  word1 = "horse", word2 = "ros"
Output: 3
Explanation:
  horse -> rorse (replace 'h' with 'r')
  rorse -> rose  (delete 'r')
  rose  -> ros   (delete 'e')

Input:  word1 = "intention", word2 = "execution"
Output: 5
```

## Constraints
- 0 <= word1.length, word2.length <= 500
- word1 and word2 consist of lowercase English letters
"""


class Solution:
    def minDistance_2d(self, word1: str, word2: str) -> int:
        # Time: O(m*n), Space: O(m*n)
        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-1], dp[i-1][j], dp[i][j-1])
        return dp[m][n]

    def minDistance(self, word1: str, word2: str) -> int:
        # dp[i][j] = min edits to convert word1[:i] to word2[:j]
        # Match: dp[i-1][j-1]; else 1 + min(insert, delete, replace)
        # Time: O(m*n), Space: O(min(m,n))
        if len(word1) < len(word2):
            word1, word2 = word2, word1
        n = len(word2)
        dp = list(range(n + 1))
        for c1 in word1:
            prev = dp[0]
            dp[0] += 1
            for j, c2 in enumerate(word2):
                temp = dp[j+1]
                dp[j+1] = prev if c1 == c2 else 1 + min(prev, dp[j+1], dp[j])
                prev = temp
        return dp[n]


if __name__ == '__main__':
    s = Solution()
    assert s.minDistance("horse", "ros") == 3
    assert s.minDistance("intention", "execution") == 5
    assert s.minDistance("", "") == 0
    assert s.minDistance("a", "") == 1
    assert s.minDistance_2d("horse", "ros") == 3
    print("All tests passed.")

"""
# 97. Interleaving String

## Problem
Given strings `s1`, `s2`, and `s3`, find whether `s3` is formed by an interleaving
of `s1` and `s2`. An interleaving of two strings s and t is a configuration where
s and t are divided into n and m substrings respectively, and the strings are
interleaved (maintaining relative order of characters from each string).

## Examples
```text
Input:  s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Input:  s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

Input:  s1 = "", s2 = "", s3 = ""
Output: true
```

## Constraints
- 0 <= s1.length, s2.length <= 100
- 0 <= s3.length <= 200
- s1, s2, and s3 consist of lowercase English letters
"""


class Solution:
    def isInterleave_2d(self, s1: str, s2: str, s3: str) -> bool:
        # Time: O(m*n), Space: O(m*n)
        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        for i in range(1, m + 1):
            dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
        for j in range(1, n + 1):
            dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or \
                            (dp[i][j-1] and s2[j-1] == s3[i+j-1])
        return dp[m][n]

    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        # dp[i][j] = can s1[:i] and s2[:j] interleave to form s3[:i+j]
        # True if (dp[i-1][j] and s1[i-1]==s3[i+j-1]) or (dp[i][j-1] and s2[j-1]==s3[i+j-1])
        # Time: O(m*n), Space: O(n)
        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False
        dp = [False] * (n + 1)
        dp[0] = True
        for j in range(1, n + 1):
            dp[j] = dp[j-1] and s2[j-1] == s3[j-1]
        for i in range(1, m + 1):
            dp[0] = dp[0] and s1[i-1] == s3[i-1]
            for j in range(1, n + 1):
                dp[j] = (dp[j] and s1[i-1] == s3[i+j-1]) or \
                         (dp[j-1] and s2[j-1] == s3[i+j-1])
        return dp[n]


if __name__ == '__main__':
    s = Solution()
    assert s.isInterleave("aabcc", "dbbca", "aadbbcbcac") == True
    assert s.isInterleave("aabcc", "dbbca", "aadbbbaccc") == False
    assert s.isInterleave("", "", "") == True
    assert s.isInterleave_2d("aabcc", "dbbca", "aadbbcbcac") == True
    print("All tests passed.")

"""
# 1049. Last Stone Weight II

## Problem
You are given an array of integers `stones` where `stones[i]` is the weight of the
i-th stone. We are playing a game with the stones. On each turn, we choose any two
stones and smash them together. If x == y, both stones are destroyed. If x != y,
the stone of weight x is destroyed and the stone of weight y has new weight y - x.
Return the smallest possible weight of the left stone (0 if all destroyed).

## Examples
```text
Input:  stones = [2,7,4,1,8,1]
Output: 1
Explanation: Combine 2 and 4 -> 2, combine 7 and 8 -> 1, combine 2 and 1 -> 1,
             combine 1 and 1 -> 0, left with 1.

Input:  stones = [31,26,33,21,40]
Output: 5
```

## Constraints
- 1 <= stones.length <= 30
- 1 <= stones[i] <= 100
"""
from typing import List


class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        # Minimize |S1 - S2| where S1+S2=total; equivalent to partition equal subset sum
        # Find largest subset sum <= total//2; answer = total - 2*that_sum
        # Time: O(n*sum), Space: O(sum)
        total = sum(stones)
        target = total // 2
        dp = {0}
        for s in stones:
            dp = {x + s for x in dp} | dp
        best = max(x for x in dp if x <= target)
        return total - 2 * best


if __name__ == '__main__':
    s = Solution()
    assert s.lastStoneWeightII([2,7,4,1,8,1]) == 1
    assert s.lastStoneWeightII([31,26,33,21,40]) == 5
    assert s.lastStoneWeightII([1]) == 1
    print("All tests passed.")

"""
# 1143. Longest Common Subsequence

## Problem
Given two strings `text1` and `text2`, return the length of their longest common
subsequence. A subsequence is a sequence derived from a string by deleting some
(or no) characters without changing the relative order of the remaining characters.

## Examples
```text
Input:  text1 = "abcde", text2 = "ace"
Output: 3
Explanation: LCS is "ace"

Input:  text1 = "abc", text2 = "abc"
Output: 3

Input:  text1 = "abc", text2 = "def"
Output: 0
```

## Constraints
- 1 <= text1.length, text2.length <= 1000
- text1 and text2 consist of only lowercase English characters
"""


class Solution:
    def longestCommonSubsequence_2d(self, text1: str, text2: str) -> int:
        # Time: O(m*n), Space: O(m*n)
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[m][n]

    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # dp[i][j] = LCS of text1[:i] and text2[:j]
        # If chars match: dp[i][j] = dp[i-1][j-1] + 1; else max of skip either
        # Time: O(m*n), Space: O(min(m,n))
        if len(text1) < len(text2):
            text1, text2 = text2, text1
        n = len(text2)
        dp = [0] * (n + 1)
        for c1 in text1:
            prev = 0
            for j, c2 in enumerate(text2):
                temp = dp[j+1]
                dp[j+1] = prev + 1 if c1 == c2 else max(dp[j+1], dp[j])
                prev = temp
        return dp[n]


if __name__ == '__main__':
    s = Solution()
    assert s.longestCommonSubsequence("abcde", "ace") == 3
    assert s.longestCommonSubsequence("abc", "abc") == 3
    assert s.longestCommonSubsequence("abc", "def") == 0
    assert s.longestCommonSubsequence_2d("abcde", "ace") == 3
    print("All tests passed.")

"""
# 329. Longest Increasing Path in a Matrix

## Problem
Given an `m x n` integers matrix, return the length of the longest increasing path.
From each cell, you can either move in four directions: left, right, up, or down.
You may not move diagonally or move outside the boundary.

## Examples
```text
Input:  matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: Longest path is [1, 2, 6, 9]

Input:  matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Explanation: Longest path is [3, 4, 5, 6]

Input:  matrix = [[1]]
Output: 1
```

## Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 200
- 0 <= matrix[i][j] <= 2^31 - 1
"""
from typing import List
from collections import deque


class Solution:
    def longestIncreasingPath_dfs(self, matrix: List[List[int]]) -> int:
        # Time: O(m*n), Space: O(m*n)
        m, n = len(matrix), len(matrix[0])
        memo = {}

        def dfs(r, c):
            if (r, c) in memo:
                return memo[(r, c)]
            best = 1
            for dr, dc in ((0,1),(0,-1),(1,0),(-1,0)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]:
                    best = max(best, 1 + dfs(nr, nc))
            memo[(r, c)] = best
            return best

        return max(dfs(r, c) for r in range(m) for c in range(n))

    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        # DFS with memoization from each cell; only move to strictly larger neighbors
        # dp[r][c] = longest path starting at (r,c)
        # Time: O(m*n), Space: O(m*n)
        m, n = len(matrix), len(matrix[0])
        dirs = [(0,1),(0,-1),(1,0),(-1,0)]
        indegree = [[0] * n for _ in range(m)]
        for r in range(m):
            for c in range(n):
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]:
                        indegree[nr][nc] += 1
        queue = deque((r, c) for r in range(m) for c in range(n) if indegree[r][c] == 0)
        length = 0
        while queue:
            length += 1
            for _ in range(len(queue)):
                r, c = queue.popleft()
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]:
                        indegree[nr][nc] -= 1
                        if indegree[nr][nc] == 0:
                            queue.append((nr, nc))
        return length


if __name__ == '__main__':
    s = Solution()
    assert s.longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]]) == 4
    assert s.longestIncreasingPath([[3,4,5],[3,2,6],[2,2,1]]) == 4
    assert s.longestIncreasingPath([[1]]) == 1
    assert s.longestIncreasingPath_dfs([[9,9,4],[6,6,8],[2,1,1]]) == 4
    print("All tests passed.")

"""
# 64. Minimum Path Sum

## Problem
Given an `m x n` grid filled with non-negative numbers, find a path from the
top-left to the bottom-right which minimizes the sum of all numbers along its path.
You can only move either down or right at any point in time.

## Examples
```text
Input:  grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Path 1→3→1→1→1 = 7

Input:  grid = [[1,2,3],[4,5,6]]
Output: 12
```

## Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 200
- 0 <= grid[i][j] <= 200
"""
from typing import List


class Solution:
    def minPathSum_2d(self, grid: List[List[int]]) -> int:
        # Time: O(m*n), Space: O(m*n)
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        return dp[m-1][n-1]

    def minPathSum(self, grid: List[List[int]]) -> int:
        # dp[i][j] = min path sum to reach (i,j) = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
        # Time: O(m*n), Space: O(n)
        m, n = len(grid), len(grid[0])
        dp = [float('inf')] * n
        dp[0] = 0
        for i in range(m):
            dp[0] += grid[i][0]
            for j in range(1, n):
                dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
        return dp[n-1]


if __name__ == '__main__':
    s = Solution()
    assert s.minPathSum([[1,3,1],[1,5,1],[4,2,1]]) == 7
    assert s.minPathSum([[1,2,3],[4,5,6]]) == 12
    assert s.minPathSum_2d([[1,3,1],[1,5,1],[4,2,1]]) == 7
    print("All tests passed.")

"""
# 10. Regular Expression Matching

## Problem
Given an input string `s` and a pattern `p`, implement regular expression matching
with support for '.' and '*' where:
- '.' matches any single character.
- '*' matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).

## Examples
```text
Input:  s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element 'a'. "aa" matches.

Input:  s = "ab", p = ".*"
Output: true
Explanation: ".*" matches any string.

Input:  s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
```

## Constraints
- 1 <= s.length <= 20
- 1 <= p.length <= 20
- s contains only lowercase English letters
- p contains only lowercase English letters, '.', and '*'
- It is guaranteed for each occurrence of '*', there will be a previous valid character to match
"""
from functools import lru_cache


class Solution:
    def isMatch_memo(self, s: str, p: str) -> bool:
        # Time: O(m*n), Space: O(m*n)
        @lru_cache(maxsize=None)
        def dp(i, j):
            if j == len(p):
                return i == len(s)
            first = i < len(s) and p[j] in (s[i], '.')
            if j + 1 < len(p) and p[j+1] == '*':
                return dp(i, j+2) or (first and dp(i+1, j))
            return first and dp(i+1, j+1)
        return dp(0, 0)

    def isMatch(self, s: str, p: str) -> bool:
        # dp[i][j] = does s[:i] match p[:j]
        # '*' can match zero (dp[i][j-2]) or more (dp[i-1][j] if chars match)
        # Time: O(m*n), Space: O(m*n)
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        for j in range(1, n + 1):
            if p[j-1] == '*' and j >= 2:
                dp[0][j] = dp[0][j-2]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j-1] == '*':
                    dp[i][j] = dp[i][j-2]  # zero occurrences
                    if p[j-2] in (s[i-1], '.'):
                        dp[i][j] = dp[i][j] or dp[i-1][j]
                elif p[j-1] in (s[i-1], '.'):
                    dp[i][j] = dp[i-1][j-1]
        return dp[m][n]


if __name__ == '__main__':
    s = Solution()
    assert s.isMatch("aa", "a*") == True
    assert s.isMatch("ab", ".*") == True
    assert s.isMatch("aa", "a") == False
    assert s.isMatch("aab", "c*a*b") == True
    assert s.isMatch("mississippi", "mis*is*p*.") == False
    assert s.isMatch_memo("aa", "a*") == True
    assert s.isMatch_memo("ab", ".*") == True
    print("All tests passed.")

"""
# 877. Stone Game

## Problem
Alice and Bob play a game with piles of stones. There are an even number of piles
arranged in a row, and each pile has a positive integer number of stones. The total
number of stones is odd. Alice and Bob take turns, with Alice going first. Each turn,
a player takes the entire pile of stones from either the beginning or the end of the
row. The player with the most stones at the end wins. Assuming Alice and Bob play
optimally, return true if Alice wins the game, or false if Bob wins.

## Examples
```text
Input:  piles = [5,3,4,5]
Output: true
Explanation: Alice starts first. Alice takes 5 (right). Bob takes 5 (left).
             Alice takes 4. Bob takes 3. Alice has 9, Bob has 8. Alice wins.

Input:  piles = [3,7,2,3]
Output: true
```

## Constraints
- 2 <= piles.length <= 500
- piles.length is even
- 1 <= piles[i] <= 500
- sum(piles[i]) is odd
"""
from typing import List


class Solution:
    def stoneGame_dp(self, piles: List[int]) -> bool:
        # Time: O(n^2), Space: O(n^2)
        n = len(piles)
        # dp[i][j] = max score difference (current player - other) for piles[i..j]
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = piles[i]
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
        return dp[0][n-1] > 0

    def stoneGame(self, piles: List[int]) -> bool:
        # Alice always wins with optimal play (mathematical proof)
        # Or dp[i][j] = max score difference for current player on piles[i..j]
        # Time: O(1), Space: O(1)
        return True  # Alice always wins with even piles and odd total


if __name__ == '__main__':
    s = Solution()
    assert s.stoneGame([5,3,4,5]) == True
    assert s.stoneGame([3,7,2,3]) == True
    assert s.stoneGame_dp([5,3,4,5]) == True
    assert s.stoneGame_dp([3,7,2,3]) == True
    print("All tests passed.")

"""
# 1140. Stone Game II

## Problem
Alice and Bob continue their games with piles of stones. There are a number of piles
arranged in a row, and each pile has a positive integer number of stones. Alice and
Bob take turns, with Alice going first. On each player's turn, that player can take
all the stones in the first X remaining piles, where 1 <= X <= 2M. Then M = max(M, X).
Initially M = 1. The goal is to maximize the number of stones Alice gets.

## Examples
```text
Input:  piles = [2,7,9,4,4]
Output: 10
Explanation: Alice takes 2 piles (2+7=9), M becomes 2.
             Bob takes 4 piles (9+4+4=17), M becomes 4.
             Alice has 9, Bob has 17... wait, Alice takes first 2 piles = 2+7=9,
             then Bob takes all remaining = 9+4+4=17? No:
             Alice takes 2 (X=2, M=2), Bob takes 4 (X=4, M=4), Alice gets 2+7=9,
             Bob gets 9+4+4=17. Actually optimal: Alice takes 1 pile (2), M=1,
             Bob takes 2 piles (7+9=16), M=2, Alice takes 4 piles (4+4=8)... 
             Optimal: Alice=10, Bob=16.

Input:  piles = [1,2,3,4,5,100]
Output: 104
```

## Constraints
- 1 <= piles.length <= 100
- 1 <= piles[i] <= 10^4
"""
from typing import List
from functools import lru_cache


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        # dp[i][m] = max stones current player can get from piles[i:] with M=m
        # Try taking x piles (1 <= x <= 2*m); update M = max(m, x)
        # Time: O(n^3), Space: O(n^2)
        n = len(piles)
        suffix = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            suffix[i] = suffix[i+1] + piles[i]

        @lru_cache(maxsize=None)
        def dp(i, M):
            if i + 2 * M >= n:
                return suffix[i]
            return suffix[i] - min(dp(i + x, max(M, x)) for x in range(1, 2 * M + 1))

        return dp(0, 1)


if __name__ == '__main__':
    s = Solution()
    assert s.stoneGameII([2,7,9,4,4]) == 10
    assert s.stoneGameII([1,2,3,4,5,100]) == 104
    print("All tests passed.")

"""
# 494. Target Sum

## Problem
You are given an integer array `nums` and an integer `target`. You want to build an
expression out of nums by adding one of the symbols '+' and '-' before each integer
in nums and then concatenate all the integers. Return the number of different
expressions that you can build which evaluates to `target`.

## Examples
```text
Input:  nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: -1+1+1+1+1 = 3, +1-1+1+1+1 = 3, +1+1-1+1+1 = 3,
             +1+1+1-1+1 = 3, +1+1+1+1-1 = 3

Input:  nums = [1], target = 1
Output: 1
```

## Constraints
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000
- 0 <= sum(nums[i]) <= 1000
- -1000 <= target <= 1000
"""
from typing import List


class Solution:
    def findTargetSumWays_brute(self, nums: List[int], target: int) -> int:
        # Time: O(2^n), Space: O(n) recursion stack
        def dfs(i, curr):
            if i == len(nums):
                return 1 if curr == target else 0
            return dfs(i+1, curr + nums[i]) + dfs(i+1, curr - nums[i])
        return dfs(0, 0)

    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # dp[i][sum] = ways to reach sum using first i numbers
        # Each number can be added (+) or subtracted (-)
        # Time: O(n*sum), Space: O(sum)
        from collections import defaultdict
        dp = defaultdict(int)
        dp[0] = 1
        for n in nums:
            next_dp = defaultdict(int)
            for s, cnt in dp.items():
                next_dp[s + n] += cnt
                next_dp[s - n] += cnt
            dp = next_dp
        return dp[target]


if __name__ == '__main__':
    s = Solution()
    assert s.findTargetSumWays([1,1,1,1,1], 3) == 5
    assert s.findTargetSumWays([1], 1) == 1
    assert s.findTargetSumWays([1], -1) == 1
    assert s.findTargetSumWays_brute([1,1,1,1,1], 3) == 5
    print("All tests passed.")

"""
# 62. Unique Paths

## Problem
A robot is located at the top-left corner of an `m x n` grid. The robot can only
move either down or right at any point in time. The robot is trying to reach the
bottom-right corner of the grid. How many possible unique paths are there?

## Examples
```text
Input:  m = 3, n = 7
Output: 28

Input:  m = 3, n = 2
Output: 3
Explanation: From top-left, 3 paths:
  1. Right -> Down -> Down
  2. Down -> Down -> Right
  3. Down -> Right -> Down
```

## Constraints
- 1 <= m, n <= 100
"""
from math import comb


class Solution:
    def uniquePaths_2d(self, m: int, n: int) -> int:
        # Time: O(m*n), Space: O(m*n)
        dp = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

    def uniquePaths_1d(self, m: int, n: int) -> int:
        # Time: O(m*n), Space: O(n)
        dp = [1] * n
        for _ in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j-1]
        return dp[n-1]

    def uniquePaths(self, m: int, n: int) -> int:
        # dp[i][j] = paths to reach (i,j) = dp[i-1][j] + dp[i][j-1]
        # Time: O(m+n), Space: O(1)
        return comb(m + n - 2, n - 1)


if __name__ == '__main__':
    s = Solution()
    assert s.uniquePaths(3, 7) == 28
    assert s.uniquePaths(3, 2) == 3
    assert s.uniquePaths(1, 1) == 1
    assert s.uniquePaths_2d(3, 7) == 28
    assert s.uniquePaths_1d(3, 7) == 28
    print("All tests passed.")

"""
# 63. Unique Paths II

## Problem
You are given an `m x n` integer array `obstacleGrid`. A robot is initially located
at the top-left corner. The robot tries to reach the bottom-right corner. An obstacle
is marked with `1` and free space with `0`. Return the number of unique paths.

## Examples
```text
Input:  obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid.
  Two ways to reach bottom-right:
  1. Right -> Right -> Down -> Down
  2. Down -> Down -> Right -> Right

Input:  obstacleGrid = [[0,1],[0,0]]
Output: 1
```

## Constraints
- m == obstacleGrid.length
- n == obstacleGrid[i].length
- 1 <= m, n <= 100
- obstacleGrid[i][j] is 0 or 1
"""
from typing import List


class Solution:
    def uniquePathsWithObstacles_2d(self, obstacleGrid: List[List[int]]) -> int:
        # Time: O(m*n), Space: O(m*n)
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            if obstacleGrid[i][0] == 1:
                break
            dp[i][0] = 1
        for j in range(n):
            if obstacleGrid[0][j] == 1:
                break
            dp[0][j] = 1
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 0:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # Same as unique paths but set dp[i][j]=0 if obstacle at (i,j)
        # Time: O(m*n), Space: O(n)
        n = len(obstacleGrid[0])
        dp = [0] * n
        dp[0] = 1
        for row in obstacleGrid:
            for j in range(n):
                if row[j] == 1:
                    dp[j] = 0
                elif j > 0:
                    dp[j] += dp[j-1]
        return dp[n-1]


if __name__ == '__main__':
    s = Solution()
    assert s.uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]]) == 2
    assert s.uniquePathsWithObstacles([[0,1],[0,0]]) == 1
    assert s.uniquePathsWithObstacles([[1]]) == 0
    assert s.uniquePathsWithObstacles_2d([[0,0,0],[0,1,0],[0,0,0]]) == 2
    print("All tests passed.")