23.07.30 Today’s Leetcode

808. Soup Servings (medium)

class Solution:
    def soupServings(self, n: int) -> float:
        if n > 4451: 
            return 1.0
        n = (n + 24) // 25
        memo = dict()
        
        def dp(i, j):
            if (i, j) in memo:
                return memo[(i, j)]
            if i <= 0 and j <= 0: 
                return 0.5
            if i <= 0: 
                return 1.0
            if j <= 0: 
                return 0.0
            memo[(i, j)] = 0.25 * (dp(i - 4, j) + dp(i - 3, j - 1) + dp(i - 2, j - 2) + dp(i - 1, j - 3))
            return memo[(i, j)]
        
        return dp(n, n)

664. Strange Printer (hard)

Failed with DFS

class Solution:
    def strangePrinter(self, s: str) -> int:

        d = defaultdict(list)
        for i, c in enumerate(s):
            d[c].append(i)
        
        n = len(s)

        def dfs(start, end):
            print(start, end)
            if start > end:
                return math.inf
            cur = s[start]
            temp = math.inf

            i = 0
            while d[cur][i] < start:
                i += 1

            while i + 1 < len(d[cur]) and d[cur][i + 1] - d[cur][i] == 1:
                i += 1

            if i == end:
                return 1

            temp = min(temp, dfs(i + 1, end))
            p = 0
            for j in range(i, len(d[cur]) - 1):
                a, b = d[cur][j], d[cur][j + 1]
                p += dfs(a + 1, b - 1)
                temp = min(temp, p + dfs(b + 1, end))
            
            return temp + 1
    
        return dfs(0, n - 1)

Failed at 110/220

class Solution:
    def strangePrinter(self, s: str) -> int:

        if len(set(s)) == 1:
            return 1

        def dfs(index):
            n = len(s)  
            key = s[index]
            temp = 0
            i = 0
            while i < n:
                if s[i] == key:
                    i += 1
                    continue
                j = i
                while j < n and s[j] != key:
                    j += 1
                temp += self.strangePrinter(s[i:j])
                i = j

            return temp + 1

        
        res = math.inf
        for i in range(len(s)):
            res = min(res, dfs(i))

        return res

DP Solution

class Solution:
    def strangePrinter(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        
        for i in range(n - 1, -1, -1):
            dp[i][i] = 1
            for j in range(i + 1, n):
                dp[i][j] = dp[i][j - 1] + 1
                for k in range(i, j):
                    if s[k] == s[j]:
                        dp[i][j] = min(dp[i][j], dp[i][k] + (dp[k + 1][j - 1] if k + 1 <= j - 1 else 0))

        return dp[0][n - 1]