2-D Dynamic Programming

本記事は以下記事の一部です。

NeetCode 150 全問の解き方とポイントまとめ & 感想

2-Dも1-Dと比較して特別難しいという印象はない。(Hard問題はやっぱり難しいけど)

126. Unique Paths

Problem

There is an m x n grid where you are allowed to move either down or to the right at any point in time.

Given the two integers m and n, return the number of possible unique paths that can be taken from the top-left corner of the grid (grid[0][0]) to the bottom-right corner (grid[m - 1][n - 1]).

You may assume the output will fit in a 32-bit integer.

Example 1:

Input: m = 3, n = 6

Output: 21

Copy

Example 2:

Input: m = 3, n = 3

Output: 6

Copy

Constraints:

• 1 <= m, n <= 100

Solution

再帰 O(2^(M+N))

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        
        def dfs(r: int, c: int) -> int:
            if r == 0 or c == 0:
                # 壁際はまっすぐ進むしかない
                return 1
            
            from_up = dfs(r-1, c)
            from_left = dfs(r, c-1)

            return from_up + from_left
        
        return dfs(m-1, n-1)

メモ化 (Top Down) O(M * N)

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

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

        for c in range(n):
            dp[0][c] = 1
        
        def dfs(r: int, c: int) -> int:
            if dp[r][c] != -1:
                return dp[r][c]
            
            from_up = dfs(r-1, c)
            from_left = dfs(r, c-1)

            dp[r][c] = from_up + from_left
            return dp[r][c]
        
        return dfs(m-1, n-1)

Tabulation (Bottom Up) O(M * N)

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

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

        for c in range(n):
            dp[0][c] = 1
        
        for r in range(1, m):
            for c in range(1, n):
                dp[r][c] = dp[r-1][c] + dp[r][c-1]
        
        return dp[m-1][n-1]

127. Longest Common Subsequence

Problem

Given two strings text1 and text2, return the length of the longest common subsequence between the two strings if one exists, otherwise return 0.

A subsequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the relative order of the remaining characters.

• For example, "cat" is a subsequence of "crabt".

A common subsequence of two strings is a subsequence that exists in both strings.

Example 1:

Input: text1 = "cat", text2 = "crabt" 

Output: 3 

Copy

Explanation: The longest common subsequence is "cat" which has a length of 3.

Example 2:

Input: text1 = "abcd", text2 = "abcd"

Output: 4

Copy

Example 3:

Input: text1 = "abcd", text2 = "efgh"

Output: 0

Copy

Constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

Solution

再帰 O(2^M + 2^N)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        def dfs(i: int, j: int) -> int:
            if i < 0 or j < 0:
                return 0
            
            res = 0
            if text1[i] == text2[j]:
                res = 1 + dfs(i-1, j-1)
            else:
                res = max(dfs(i-1, j), dfs(i, j-1))
            
            return res
        
        return dfs(len(text1)-1, len(text2)-1)

メモ化 (Top Down) O(M * N)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = {} # (i, j) -> longest common subsequence
        
        def dfs(i: int, j: int) -> int:
            if i < 0 or j < 0:
                return 0
            
            if (i,j) in dp:
                return dp[(i,j)]

            res = 0
            if text1[i] == text2[j]:
                res = 1 + dfs(i-1, j-1)
            else:
                res = max(dfs(i-1, j), dfs(i, j-1))
            
            dp[(i,j)] = res
            return dp[(i,j)]
        
        return dfs(len(text1)-1, len(text2)-1)

Tabulation (Bottom Up) O(M * N)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = {} # (i, j) -> longest common subsequence
        
        # Tabulationの場合はマイナスの値は扱えないので
        # 右に一つshiftする
        dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]

        # どちらかが0の場合は0
        for i in range(len(text1)+1):
            dp[i][0] = 0
        
        for j in range(len(text2)+1):
            dp[0][j] = 0
        
        for i in range(1, len(text1)+1):
            for j in range(1, len(text2)+1):
                if text1[i-1] == text2[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[len(text1)][len(text2)]

128. Best Time to Buy And Sell Stock With Cooldown

Problem

Given two strings text1 and text2, return the length of the longest common subsequence between the two strings if one exists, otherwise return 0.

A subsequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the relative order of the remaining characters.

• For example, "cat" is a subsequence of "crabt".

A common subsequence of two strings is a subsequence that exists in both strings.

Example 1:

Input: text1 = "cat", text2 = "crabt" 

Output: 3 

Copy

Explanation: The longest common subsequence is "cat" which has a length of 3.

Example 2:

Input: text1 = "abcd", text2 = "abcd"

Output: 4

Copy

Example 3:

Input: text1 = "abcd", text2 = "efgh"

Output: 0

Copy

Constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

Solution

再帰 O(3^N)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        def dfs(i: int, state: int) -> int:
            if i == len(prices):
                # 取引終了
                return 0
            
            # 買える状態
            res = 0
            if state == 0:
                # 買う (買った直後の状態に遷移)
                buy = -prices[i] + dfs(i+1, 1)
                # 買わない (買える状態のまま遷移)
                not_buy = dfs(i+1, 0)

                res = max(buy, not_buy)
            # 買った直後の状態
            elif state == 1:
                # 売る (売った直後の状態(cool)に遷移)
                sell = prices[i] + dfs(i+1, 2)

                # 売らない (売れる状態のまま遷移)
                not_sell = dfs(i+1, 1)

                res = max(sell, not_sell)
            # coolの状態
            else:
                # 何もせずに進むしかない
                # (買える状態に遷移)
                res = dfs(i+1, 0)
            
            return res
        
        return dfs(0, 0)

メモ化 (Top Down) O(N)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = {} # (i, state) -> profit
        
        def dfs(i: int, state: int) -> int:
            if i == len(prices):
                # 取引終了
                return 0
            
            if (i, state) in dp:
                return dp[(i, state)]
            
            # 買える状態
            res = 0
            if state == 0:
                # 買う (買った直後の状態に遷移)
                buy = -prices[i] + dfs(i+1, 1)
                # 買わない (買える状態のまま遷移)
                not_buy = dfs(i+1, 0)

                res = max(buy, not_buy)
            # 買った直後の状態
            elif state == 1:
                # 売る (売った直後の状態(cool)に遷移)
                sell = prices[i] + dfs(i+1, 2)

                # 売らない (売れる状態のまま遷移)
                not_sell = dfs(i+1, 1)

                res = max(sell, not_sell)
            # coolの状態
            else:
                # 何もせずに進むしかない
                # (買える状態に遷移)
                res = dfs(i+1, 0)
            
            dp[(i, state)] = res
            
            return dp[(i, state)]
        
        return dfs(0, 0)

Tabulation (Bottom Up) O(N)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [[-1] * 3 for _ in range(len(prices)+1)]
        for j in range(3):
            dp[len(prices)][j] = 0
        
        for i in range(len(prices)-1, -1, -1):
            for j in range(3):
                # 買える状態
                if j == 0:
                    # 買う (買った直後の状態に遷移)
                    buy = -prices[i] + dp[i+1][1]
                    # 買わない (買える状態のまま遷移)
                    not_buy = dp[i+1][0]
                    dp[i][j] = max(buy, not_buy)
                # 買った直後の状態
                elif j == 1:
                    # 売る (売った直後の状態(cool)に遷移)
                    sell = prices[i] + dp[i+1][2]

                    # 売らない (売れる状態のまま遷移)
                    not_sell = dp[i+1][1]

                    dp[i][j] = max(sell, not_sell)
                # coolの状態
                else:
                    # 何もせずに進むしかない
                    # (買える状態に遷移)
                    dp[i][j] = dp[i+1][0]
        
        return dp[0][0]

129. Coin Change II

Problem

You are given an integer array coins representing coins of different denominations (e.g. 1 dollar, 5 dollars, etc) and an integer amount representing a target amount of money.

Return the number of distinct combinations that total up to amount. If it's impossible to make up the amount, return 0.

You may assume that you have an unlimited number of each coin and that each value in coins is unique.

Example 1:

Input: amount = 4, coins = [1,2,3]

Output: 4

Copy

Explanation:

• 1+1+1+1 = 4
• 1+1+2 = 4
• 2+2 = 4
• 1+3 = 4

Example 2:

Input: amount = 7, coins = [2,4]

Output: 0

Copy

Constraints:

• 1 <= coins.length <= 100
• 1 <= coins[i] <= 1000
• 0 <= amount <= 1000

Solution

再帰 O(2^(N+M))

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        
        def dfs(i: int, a: int) -> int:
            if a == amount:
                return 1
            
            if a > amount or i >= len(coins):
                return 0
            
            res = 0
            # pick and stay
            res += dfs(i, a + coins[i])

            # not pick and go
            res += dfs(i + 1, a)

            return res
        
        return dfs(0, 0)

メモ化 (Top Down) O(N*M)

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = {} # (i, a) -> ways
        
        def dfs(i: int, a: int) -> int:
            if a == amount:
                return 1
            
            if a > amount or i >= len(coins):
                return 0
            
            if (i, a) in dp:
                return dp[(i,a)]
            
            res = 0
            # pick and stay
            res += dfs(i, a + coins[i])

            # not pick and go
            res += dfs(i + 1, a)

            dp[(i,a)] = res

            return dp[(i,a)]
        
        return dfs(0, 0)

Tabulation (Bottom Up) O(N * M)

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = {} # (i, a) -> ways
        dp = [[0] * (amount+1) for _ in range(len(coins) + 1)]

        for i in range(len(coins)+1):
            dp[i][amount] = 1
        
        for i in range(len(coins)-1, -1, -1):
            for j in range(amount-1, -1, -1):
                dp[i][j] = dp[i+1][j]
                if j + coins[i] <= amount:
                    dp[i][j] += dp[i][j + coins[i]]
        
        return dp[0][0]

130. Target Sum

Problem

You are given an array of integers nums and an integer target.

For each number in the array, you can choose to either add or subtract it to a total sum.

• For example, if nums = [1, 2], one possible sum would be "+1-2=-1".

If nums=[1,1], there are two different ways to sum the input numbers to get a sum of 0: "+1-1" and "-1+1".

Return the number of different ways that you can build the expression such that the total sum equals target.

Example 1:

Input: nums = [2,2,2], target = 2

Output: 3

Copy

Explanation: There are 3 different ways to sum the input numbers to get a sum of 2.
+2 +2 -2 = 2
+2 -2 +2 = 2
-2 +2 +2 = 2

Constraints:

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• -1000 <= target <= 1000

Solution

再帰 O(2^N)

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        
        def dfs(i: int, total: int) -> int:
            if i >= len(nums):
                if total == target:
                    return 1
                return 0
            
            res = 0
            # plus
            res += dfs(i+1, total + nums[i])

            # minus
            res += dfs(i+1, total - nums[i])
        
            return res
        
        return dfs(0, 0)

メモ化 (Top Down) O(N*M)

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        dp = {} # (i, total) -> ways
        
        def dfs(i: int, total: int) -> int:
            if i >= len(nums):
                if total == target:
                    return 1
                return 0
            
            if (i, total) in dp:
                return dp[(i, total)]
            
            res = 0
            # plus
            res += dfs(i+1, total + nums[i])

            # minus
            res += dfs(i+1, total - nums[i])

            dp[(i, total)] = res
        
            return dp[(i, total)]
        
        return dfs(0, 0)

131. Interleaving String

Problem

You are given three strings s1, s2, and s3. Return true if s3 is formed by interleaving s1 and s2 together or false otherwise.

Interleaving two strings s and t is done by dividing s and t into n and m substrings respectively, where the following conditions are met

• |n - m| <= 1, i.e. the difference between the number of substrings of s and t is at most 1.
• s = s1 + s2 + ... + sn
• t = t1 + t2 + ... + tm
• Interleaving s and t is s1 + t1 + s2 + t2 + ... or t1 + s1 + t2 + s2 + ...

You may assume that s1, s2 and s3 consist of lowercase English letters.

Example 1:

Input: s1 = "aaaa", s2 = "bbbb", s3 = "aabbbbaa"

Output: true

Copy

Explanation: We can split s1 into ["aa", "aa"], s2 can remain as "bbbb" and s3 is formed by interleaving ["aa", "aa"] and "bbbb".

Example 2:

Input: s1 = "", s2 = "", s3 = ""

Output: true

Copy

Example 3:

Input: s1 = "abc", s2 = "xyz", s3 = "abxzcy"

Output: false

Copy

Explanation: We can't split s3 into ["ab", "xz", "cy"] as the order of characters is not maintained.

Constraints:

• 0 <= s1.length, s2.length <= 50
• 0 <= s3.length <= 100

Solution

再帰 O(2^(N+M))

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False

        def dfs(i: int, j: int) -> bool:
            if i + j == len(s3):
                return True

            res = False
            # s1と等しい時
            if i < len(s1) and s1[i] == s3[i+j]:
                # pick (s1を選んで進む)
                if dfs(i+1, j):
                    res = True

            # s2と等しい時
            if j < len(s2) and s2[j] == s3[i+j]:
                # pick (s2を選んで進む)
                if dfs(i, j+1):
                    res = True
                
            return res
        
        return dfs(0, 0)

メモ化 (Top Down) O(N*M)

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False

        dp = {} # (i, j) -> bool
        
        def dfs(i: int, j: int) -> bool:
            if i + j == len(s3):
                return True

            if (i, j) in dp:
                return dp[(i, j)]
            
            res = False
            # s1と等しい時
            if i < len(s1) and s1[i] == s3[i+j]:
                # pick (s1を選んで進む)
                if dfs(i+1, j):
                    res = True

            # s2と等しい時
            if j < len(s2) and s2[j] == s3[i+j]:
                # pick (s2を選んで進む)
                if dfs(i, j+1):
                    res = True
                
            dp[(i,j)] = res
            return dp[(i,j)]
        
        return dfs(0, 0)

Tabulation (Bottom up) O(N*M)

TBD

132. Edit Distance

Problem

You are given two strings word1 and word2, each consisting of lowercase English letters.

You are allowed to perform three operations on word1 an unlimited number of times:

• Insert a character at any position
• Delete a character at any position
• Replace a character at any position

Return the minimum number of operations to make word1 equal word2.

Example 1:

Input: word1 = "monkeys", word2 = "money"

Output: 2

Copy

Explanation:
monkeys -> monkey (remove s)
monkey -> monkey (remove k)

Example 2:

Input: word1 = "neatcdee", word2 = "neetcode"

Output: 3

Copy

Explanation:
neatcdee -> neetcdee (replace a with e)
neetcdee -> neetcde (remove last e)
neetcde -> neetcode (insert o)

Constraints:

• 0 <= word1.length, word2.length <= 100
• word1 and word2 consist of lowercase English letters.

Solution

再帰 O(2^(N+M))

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        
        def dfs(i: int, j: int) -> int:
            # ベースケース
            # どちらかのindexが最後まで行った場合は、
            # 残った文字の長さを返す
            if i == len(word1):
                return len(word2) - j
            if j == len(word2):
                return len(word1) - i
            
            if word1[i] == word2[j]:
                # 一致する場合そのまま進む
                return dfs(i+1, j+1)
            else:
                # 一致しない場合
                # replaceする
                replace = 1 + dfs(i+1, j+1)
        
                # delete
                delete = 1 + dfs(i+1, j)

                # insert
                insert = 1 + dfs(i, j+1)

                return min(replace, delete, insert)
        
        return dfs(0, 0)

メモ化 (Top Down) O(N*M)

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = {} # (i, j) -> operations
        
        def dfs(i: int, j: int) -> int:
            # ベースケース
            # どちらかのindexが最後まで行った場合は、
            # 残った文字の長さを返す
            if i == len(word1):
                return len(word2) - j
            if j == len(word2):
                return len(word1) - i
            
            if (i,j) in dp:
                return dp[(i,j)]
            
            if word1[i] == word2[j]:
                # 一致する場合そのまま進む
                res = dfs(i+1, j+1)
                dp[(i,j)] = res
                return dp[(i,j)]
            else:
                # 一致しない場合
                # replaceする
                replace = 1 + dfs(i+1, j+1)
        
                # delete
                delete = 1 + dfs(i+1, j)

                # insert
                insert = 1 + dfs(i, j+1)

                dp[(i,j)] = min(replace, delete, insert)

                return dp[(i,j)]
        
        return dfs(0, 0)

Tabulation (Bottom up) O(N*M)

TBD

133. Longest Increasing Path In a Matrix

Problem

You are given two strings word1 and word2, each consisting of lowercase English letters.

You are allowed to perform three operations on word1 an unlimited number of times:

• Insert a character at any position
• Delete a character at any position
• Replace a character at any position

Return the minimum number of operations to make word1 equal word2.

Example 1:

Input: word1 = "monkeys", word2 = "money"

Output: 2

Copy

Explanation:
monkeys -> monkey (remove s)
monkey -> monkey (remove k)

Example 2:

Input: word1 = "neatcdee", word2 = "neetcode"

Output: 3

Copy

Explanation:
neatcdee -> neetcdee (replace a with e)
neetcdee -> neetcde (remove last e)
neetcde -> neetcode (insert o)

Constraints:

• 0 <= word1.length, word2.length <= 100
• word1 and word2 consist of lowercase English letters.

Solution

再帰 O(4^(N*M))

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        DIRECTIONS = [[-1,0],[0,1],[1,0],[0,-1]]
        visited = set()
        
        def dfs(r: int, c: int, last_val: int) -> int:
            if (r not in range(ROWS) or
                c not in range(COLS) or
                (r,c) in visited or
                matrix[r][c] >= last_val
                ):
                return 0
            
            res = 1
            visited.add((r,c))
            for dr, dc in DIRECTIONS:
                nr, nc = r + dr, c + dc
                tmp_res = 1 + dfs(nr, nc, matrix[r][c])
                res = max(res, tmp_res)

            visited.remove((r,c))

            return res
        
        longest = 1
        for r in range(ROWS):
            for c in range(COLS):
                res = dfs(r, c, math.inf)
                print(r,c,res)
                longest = max(longest, res)

        return longest

メモ化 (Top Down) O(N*M)

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        DIRECTIONS = [[-1,0],[0,1],[1,0],[0,-1]]
        visited = set()

        dp = {} #(r,c) -> lipm
        
        def dfs(r: int, c: int, last_val: int) -> int:
            if (r not in range(ROWS) or
                c not in range(COLS) or
                (r,c) in visited or
                matrix[r][c] >= last_val
                ):
                return 0
            
            if (r,c) in dp:
                return dp[(r,c)]
            
            res = 1
            visited.add((r,c))
            for dr, dc in DIRECTIONS:
                nr, nc = r + dr, c + dc
                tmp_res = 1 + dfs(nr, nc, matrix[r][c])
                res = max(res, tmp_res)

            visited.remove((r,c))

            dp[(r,c)] = res
            return dp[(r,c)]
        
        longest = 1
        for r in range(ROWS):
            for c in range(COLS):
                res = dfs(r, c, math.inf)
                longest = max(longest, res)

        return longest

Tabulation (Bottom up) O(N*M)

TBD

134. Distinct Subsequences

Problem

You are given two strings s and t, both consisting of english letters.

Return the number of distinct subsequences of s which are equal to t.

Example 1:

Input: s = "caaat", t = "cat"

Output: 3

Copy

Explanation: Rhere are 3 ways you can generate "cat" from s.

• (c)aa(at)
• (c)a(a)a(t)
• (ca)aa(t)

Example 2:

Input: s = "xxyxy", t = "xy"

Output: 5

Copy

Explanation: There are 5 ways you can generate "xy" from s.

• (x)x(y)xy
• (x)xyx(y)
• x(x)(y)xy
• x(x)yx(y)
• xxy(x)(y)

Constraints:

• 1 <= s.length, t.length <= 1000
• s and t consist of English letters.

Solution

再帰 O(2^(N+M))

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        if len(t) > len(s):
            return 0
        
        def dfs(i: int, j: int) -> int:
            if j == len(t):
                return 1
            
            if i == len(s):
                return 0
            
            res = 0
            # 現在の文字が一致
            if s[i] == t[j]:
                # 選んで両方進む
                res += dfs(i+1, j+1)
                # 選ばずにsだけ進む
                res += dfs(i+1, j)
            else:
                # 選べないのでsだけ進む
                res += dfs(i+1, j)
            
            return res
        
        return dfs(0, 0)

メモ化 (Top Down) O(N*M)

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        if len(t) > len(s):
            return 0

        dp = {}
        
        def dfs(i: int, j: int) -> int:
            if j == len(t):
                return 1
            
            if i == len(s):
                return 0
            
            if (i, j) in dp:
                return dp[(i,j)]
            
            res = 0
            # 現在の文字が一致
            if s[i] == t[j]:
                # 選んで両方進む
                res += dfs(i+1, j+1)
                # 選ばずにsだけ進む
                res += dfs(i+1, j)
            else:
                # 選べないのでsだけ進む
                res += dfs(i+1, j)
            
            dp[(i,j)] = res
            
            return dp[(i,j)]
        
        return dfs(0, 0)

Tabulation (Bottom up) O(N*M)

TBD

135. Burst Balloons

Problem

You are given an array of integers nums of size n. The ith element represents a balloon with an integer value of nums[i]. You must burst all of the balloons.

If you burst the ith balloon, you will receive nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then assume the out of bounds value is 1.

Return the maximum number of coins you can receive by bursting all of the balloons.

Example 1:

Input: nums = [4,2,3,7]

Output: 167

Explanation:
nums = [4,2,3,7] --> [4,3,7] --> [4,7] --> [7] --> []
coins =  4*2*3    +   4*3*7   +  1*4*7  + 1*7*1 = 143

Copy

Constraints:

• n == nums.length
• 1 <= n <= 300
• 0 <= nums[i] <= 100

Solution

再帰 O(N^3)

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]
        
        def dfs(l: int, r: int) -> int:
            if l > r:
                return 0
            
            res = -math.inf
            for i in range(l, r+1):
                coins = nums[l-1] * nums[i] * nums[r+1]
                coins += dfs(l,i-1)
                coins += dfs(i+1,r)
                res = max(res, coins)
            return res

        return dfs(1, len(nums)-2)

メモ化 (Top Down) O(N^2)

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]
        
        dp = {}

        def dfs(l: int, r: int) -> int:
            if l > r:
                return 0
            
            if (l,r) in dp:
                return dp[(l,r)]
            
            res = -math.inf
            for i in range(l, r+1):
                coins = nums[l-1] * nums[i] * nums[r+1]
                coins += dfs(l,i-1)
                coins += dfs(i+1,r)
                res = max(res, coins)
            
            dp[(l,r)] = res
            return dp[(l,r)]

        return dfs(1, len(nums)-2)

Tabulation (Bottom up) O(N*M)

TBD

136. Regular Expression Matching

Problem

You are given an input string s consisting of lowercase english letters, and a pattern p consisting of lowercase english letters, as well as '.', and '*' characters.

Return true if the pattern matches the entire input string, otherwise return false.

• '.' Matches any single character
• '*' Matches zero or more of the preceding element.

Example 1:

Input: s = "aa", p = ".b"

Output: false

Copy

Explanation: Regardless of which character we choose for the '.' in the pattern, we cannot match the second character in the input string.

Example 2:

Input: s = "nnn", p = "n*"

Output: true

Copy

Explanation: '*' means zero or more of the preceding element, 'n'. We choose 'n' to repeat three times.

Example 3:

Input: s = "xyz", p = ".*z"

Output: true

Copy

Explanation: The pattern ".*" means zero or more of any character, so we choose ".." to match "xy" and "z" to match "z".

Constraints:

• 1 <= s.length <= 20
• 1 <= p.length <= 20
• Each appearance of '*', will be preceded by a valid character or '.'.

Solution

再帰 O(2^(M*N))

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        
        def dfs(i: int, j: int) -> bool:
            if i == len(s) and j == len(p):
                return True
            
            if i == len(s) or j == len(p):
                return False

            # マッチする場合
            if s[i] == p[j] or p[j] == '.':
                # 次の文字が*の場合
                if j+1 < len(p) and p[j+1] == '*':
                    # *を使う場合
                    if dfs(i+1, j):
                        return True
                    
                    # *は空でも良いので、使わないこともできる
                    if dfs(i, j+2):
                        return True
                    return dfs(i+1, j+2)
                # 次の文字が*以外の場合
                else:
                    return dfs(i+1, j+1)
            # マッチしない場合
            else:
                # 次の文字が*の場合、その文字を一切使わない選択肢がある
                if j+1 < len(p) and p[j+1] == '*':
                    return dfs(i, j+2)
            
            return False
        
        return dfs(0 ,0)

メモ化 (Top Down) O(M*N)

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        dp = {}
        
        def dfs(i: int, j: int) -> bool:
            if i == len(s) and j == len(p):
                return True
            
            if i == len(s) or j == len(p):
                return False
            
            if (i,j) in dp:
                return dp[(i,j)]
        
            # マッチする場合
            if s[i] == p[j] or p[j] == '.':
                # 次の文字が*の場合
                if j+1 < len(p) and p[j+1] == '*':
                    # *を使う場合
                    if dfs(i+1, j):
                        dp[(i,j)] = True
                        return True
                    
                    # *は空でも良いので、使わないこともできる
                    if dfs(i, j+2):
                        dp[(i,j)] = True
                        return True
                    
                    
                    if dfs(i+1, j+2):
                        dp[(i,j)] = True
                        return True
                    
                # 次の文字が*以外の場合
                else:
                    if dfs(i+1, j+1):
                        dp[(i,j)] = True
                        return True
            # マッチしない場合
            else:
                # 次の文字が*の場合、その文字を一切使わない選択肢がある
                if j+1 < len(p) and p[j+1] == '*':
                    if dfs(i, j+2):
                        dp[(i,j)] = True
                        return True
            
            dp[(i,j)] = False
            return False
        
        return dfs(0 ,0)

Tabulation (Bottom up) O(N*M)

TBD