# dp[i] = number of ways to reach step i
# dp[i] = dp[i-1] + dp[i-2]

def climbStairs(n):
    if n <= 2: return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

# dp[i] = number of ways to decode s[0..i-1]
# Single digit valid: s[i-1] in '1'..'9'  → dp[i] += dp[i-1]
# Two digits valid:   s[i-2..i-1] in 10..26 → dp[i] += dp[i-2]

def numDecodings(s):
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1 if s[0] != '0' else 0

    for i in range(2, n + 1):
        one  = int(s[i - 1])
        two  = int(s[i - 2:i])
        if 1 <= one <= 9:   dp[i] += dp[i - 1]
        if 10 <= two <= 26: dp[i] += dp[i - 2]

    return dp[n]

# numDecodings("226") → 3  ("2,2,6" / "22,6" / "2,26")

# O(n²) DP
def lengthOfLIS_n2(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# O(n log n) — maintain `tails`: smallest tail for each LIS length
# tails[i] = smallest ending element of any increasing subsequence of length i+1
import bisect

def lengthOfLIS(nums):
    tails = []
    for n in nums:
        pos = bisect.bisect_left(tails, n)   # first index where tails[pos] >= n
        if pos == len(tails):
            tails.append(n)        # extend longest subsequence
        else:
            tails[pos] = n         # replace to keep tail as small as possible
    return len(tails)

# lengthOfLIS([10,9,2,5,3,7,101,18]) → 4  ([2,3,7,101])

# dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1]
# Match:    dp[i][j] = 1 + dp[i-1][j-1]
# No match: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

def longestCommonSubsequence(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

# dp[i][j] = min ops to convert s[0..i-1] → t[0..j-1]
# Base:  dp[i][0] = i  (delete all),  dp[0][j] = j  (insert all)
# Match: dp[i][j] = dp[i-1][j-1]
# Else:  dp[i][j] = 1 + min(replace, delete, insert)

def minDistance(s, t):
    m, n = len(s), len(t)
    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 s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1],  # replace
                                    dp[i - 1][j],       # delete from s
                                    dp[i][j - 1])       # insert into s
    return dp[m][n]

# dp[i][j] = can we make sum j using elements 0..i-1?
# Include: dp[i-1][j - A[i-1]]  (if j >= A[i-1])
# Exclude: dp[i-1][j]

def canPartition(nums):
    total = sum(nums)
    if total % 2: return False
    target = total // 2

    dp = [False] * (target + 1)
    dp[0] = True                   # sum 0 always reachable

    for num in nums:
        for j in range(target, num - 1, -1):   # reverse to avoid reuse
            dp[j] = dp[j] or dp[j - num]

    return dp[target]

# canPartition([1,5,11,5]) → True  ([1,5,5] and [11])

# Full 2-D version (explicit, easier to reason about)
def subsetSum(A, target):
    n = len(A)
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    for i in range(n + 1): dp[i][0] = True   # sum 0 always reachable

    for i in range(1, n + 1):
        for j in range(1, target + 1):
            dp[i][j] = dp[i - 1][j]                            # exclude
            if j >= A[i - 1]:
                dp[i][j] = dp[i][j] or dp[i - 1][j - A[i - 1]]  # include
    return dp[n][target]

# dp[i] = min coins to make amount i
# dp[0] = 0;  dp[i] = min over all coins c: dp[i-c] + 1

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for c in coins:
            if c <= i:
                dp[i] = min(dp[i], dp[i - c] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

# coinChange([1,5,11], 15) → 3  (5+5+5 not 11+...) wait → actually 15=11+... hmm
# coinChange([1,5,11], 15) → 3  (5+5+5)

# dp[i][j] = min cost to reach cell (i, j)
# dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

def minPathSum(grid):
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = grid[0][0]

    for j in range(1, cols): dp[0][j] = dp[0][j - 1] + grid[0][j]
    for i in range(1, rows): dp[i][0] = dp[i - 1][0] + grid[i][0]

    for i in range(1, rows):
        for j in range(1, cols):
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])

    return dp[rows - 1][cols - 1]

# Bottom-up: start from second-to-last row, add the min of two children below.
# Modifies triangle in-place — use a copy if needed.

def minimumTotal(triangle):
    for i in range(len(triangle) - 2, -1, -1):
        for j in range(len(triangle[i])):
            triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1])
    return triangle[0][0]

# Single transaction — track running min, update max profit
def maxProfit_once(prices):
    min_price = float('inf')
    max_profit = 0
    for p in prices:
        min_price  = min(min_price, p)
        max_profit = max(max_profit, p - min_price)
    return max_profit

# Unlimited transactions — sum all positive day-over-day gains
def maxProfit_unlimited(prices):
    return sum(max(prices[i] - prices[i - 1], 0) for i in range(1, len(prices)))

# With cooldown (LC 309) — state machine
# held[i]  = max profit on day i if holding stock
# sold[i]  = max profit on day i if just sold (must rest tomorrow)
# rest[i]  = max profit on day i if resting
def maxProfit_cooldown(prices):
    held = -float('inf')
    sold = 0
    rest = 0
    for p in prices:
        prev_sold = sold
        sold = held + p
        held = max(held, rest - p)
        rest = max(rest, prev_sold)
    return max(sold, rest)