16 posts tagged with "Dynamic Programming"

class SolutionR1:  # O(n*n) / O(n) ? str slice
    def numDecodings(self, s: str) -> int:
        m = {'': 1}

        def recur(s=s):
            if s in m:
                return m[s]
            m[s] = 0
            if s[0] != '0':
                m[s] += recur(s[1:])
            if 10 <= int(s[:2]) <= 26:
                m[s] += recur(s[2:])
            return m[s]

        return recur()


class SolutionR2:  # O(n) / O(n)
    def numDecodings(self, s: str) -> int:
        m = {len(s): 1}

        def recur(i=0):
            if i in m:
                return m[i]
            m[i] = 0
            if s[i] != '0':
                m[i] += recur(i + 1)
            if 10 <= int(s[i : i + 2]) <= 26:
                m[i] += recur(i + 2)
            return m[i]

        return recur()


class Solution1:  # O(n) / O(n)
    def numDecodings(self, s: str) -> int:
        dp = [0] * (len(s) + 1)
        dp[0], dp[1] = 1, int(s[0] != '0')
        for i in range(len(s) - 1):
            if s[i + 1] != '0':
                dp[i + 2] += dp[i + 1]
            if 10 <= int(s[i : i + 2]) <= 26:
                dp[i + 2] += dp[i]
        return dp[-1]


class Solution2:  # O(n) / O(1)
    def numDecodings(self, s: str) -> int:
        a, b = 1, int(s[0] != '0')
        for i in range(len(s) - 1):
            c = 0
            if s[i + 1] != '0':
                c += b
            if 10 <= int(s[i : i + 2]) <= 26:
                c += a
            a, b = b, c
        return b


class Solution3:  # O(n) / O(1)
    def numDecodings(self, s: str) -> int:
        a, b = 1, int(s[0] != '0')
        for i in range(len(s) - 1):
            one, two = s[i + 1] != '0', 10 <= int(s[i : i + 2]) <= 26
            a, b = b, b * one + a * two
        return b


class Solution4:  # O(n) / O(1)
    def numDecodings(self, s: str) -> int:
        a, b, p = 0, int(bool(s)), ''
        for c in s:
            tmp = b
            if c == '0':
                b = 0
            if 10 <= int(p + c) <= 26:
                b += a
            a, p = tmp, c
        return b


class Solution:  # O(n) / O(1)
    def numDecodings(self, s: str) -> int:
        a, b, p = 0, int(bool(s)), ''
        for c in s:
            one, two = c != '0', 10 <= int(p + c) <= 26
            a, b, p = b, b * one + a * two, c
        return b

'''
f(k) = (n/k)^k
-> ln(f(k)) = k ln(n/k)
-> d ln(f(k)) / d k = ln(n/k) + k(-1/k)
-> d f(k) / f(k) d k = ln(n/k) - 1
-> f′(k) = f(k) (ln(n/k) - 1)
find the maximum:
f′(k) = 0
-> ln(n/k) = 1
-> n/k = e, 2 or 3
'''


import math


class Solution1:  # O(n)
    # https://leetcode.com/problems/integer-break/solutions/4136961/easy-olog-n-time-with-o1-space-complexity-easy-math-solution-with-proofs/
    def integerBreak(self, n: int) -> int:
        if n < 4:
            return n - 1
        result = 1
        while n > 4:
            result *= 3
            n -= 3
        return n * result


class Solution2:  # O(log(n))
    def integerBreak(self, n: int) -> int:
        if n < 4:
            return n - 1
        return 2 ** (-n % 3) * 3 ** ((n - 4) // 3 + (n - 1) % 3)


class Solution:  # O(1)
    def integerBreak(self, n: int) -> int:
        if n < 4:
            return n - 1
        return int(math.pow(2, -n % 3) * math.pow(3, (n - 4) // 3 + (n - 1) % 3))

class Solution:
    def rob(self, nums: list[int]) -> int:
        def _rob(start: int, stop: int):
            a, b = 0, 0
            for i in range(start, stop):
                a, b = b, max(a + nums[i], b)
            return b

        return max(_rob(0, len(nums) - 1), _rob(1, len(nums)))

class Solution:
    def rob(self, nums: list[int]) -> int:
        a, b = 0, 0
        for n in nums:
            a, b = b, max(a + n, b)
        return b

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        dp = [0] + [0xFFFFFFFF] * (amount)
        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] = min(dp[i], dp[i - coin] + 1)
        return (dp[-1], -1)[dp[-1] == 0xFFFFFFFF]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]
        for i in range(len(text1)):
            for j in range(len(text2)):
                if text1[i] == text2[j]:
                    dp[i + 1][j + 1] = dp[i][j] + 1
                else:
                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
        return dp[-1][-1]

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        result = acc = nums[0]
        for i in range(1, len(nums)):
            acc = max(nums[i], nums[i] + acc)
            result = max(result, acc)
        return result

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        result = acc_max = acc_min = nums[0]
        for i in range(1, len(nums)):
            cand = nums[i], nums[i] * acc_max, nums[i] * acc_min
            acc_max, acc_min = max(cand), min(cand)
            result = max(result, acc_max, acc_min)
        return result

from bisect import bisect_left


class SolutionDp:  # O(n*n) / O(n)
    def lengthOfLIS(self, nums: list[int]) -> int:
        result, dp = 1, [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)
                    result = max(result, dp[i])
        return result


class SolutionBs:  # O(n*log(n)) / O(n)
    def lengthOfLIS(self, nums: list[int]) -> int:
        result, dp = 0, [0] * len(nums)
        for num in nums:
            lo = bisect_left(dp, num, hi=result)
            result, dp[lo] = max(result, lo + 1), num
        return result


class SolutionBsLessSpace:  # O(n*log(n)) / O(n)
    def lengthOfLIS(self, nums: list[int]) -> int:
        result, dp = 0, []
        for i in range(len(nums)):
            if dp and nums[i] <= dp[-1]:
                dp[bisect_left(dp, nums[i])] = nums[i]
            else:
                result += 1
                dp.append(nums[i])
        return result


class SolutionBsInPlace:  # O(n*log(n)) / O(1)
    def lengthOfLIS(self, nums: list[int]) -> int:
        result = 0
        for i in range(len(nums)):
            lo = bisect_left(nums, nums[i], hi=result)
            result, nums[lo] = max(result, lo + 1), nums[i]
        return result

class Solution:
    def mincostTickets(self, days: list[int], costs: list[int]) -> int:
        day_costs = dict(zip([1, 7, 30], costs))
        N = days[-1]
        dp = [0] * (N + 1)
        travel = set(days)
        for i in range(1, N + 1):
            if i in travel:
                dp[i] = min(dp[max(0, i - d)] + c for d, c in day_costs.items())
            else:
                dp[i] = dp[i - 1]
        return dp[-1]

class Solution:
    def findBall(self, grid: list[list[int]]) -> list[int]:
        N = len(grid[0])

        def drop(pos: int) -> int:
            for row in grid:
                adj = pos + row[pos]
                if not 0 <= adj < N:
                    return -1
                if row[pos] != row[adj]:
                    return -1
                pos = adj
            return pos

        return [drop(x) for x in range(N)]

import math


class Solution1:
    def uniquePaths(self, m: int, n: int) -> int:
        return math.comb((m - 1) + (n - 1), (n - 1))


class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1] + [0 for _ in range(n - 1)]
        for _ in range(m):
            for i in range(n - 1):
                dp[i + 1] += dp[i]
        return dp[n - 1]

class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 1, 1
        for _ in range(n):
            a, b = b, a + b
        return a

class Solution:
    def fib(self, n: int) -> int:
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a + b
        return a

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        a = b = 0
        for c in cost:
            a, b = b, min(a, b) + c
        return min(a, b)

class Solution:
    def maxProfit(self, prices) -> int:
        result, buy = 0, prices[0]
        for p in prices:
            result, buy = max(result, p - buy), min(buy, p)
        return result