1-D Dynamic Programming

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

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

他の分野は解説読むとあーなるほどとなることがほとんどだけど、DPだけはよく分からないものが多かった。カエルがどうとか、階段がどうとかは全然分かるんだけど、ちょっと発展した問題になるとよく分からなくなっていた。

Redditで Dynamic Programming Playlist - Striver が結構おすすめされてたのでいくつか見てみたら確かに分かりやすく、だいぶ理解が進んだ気がする。(全部見ると果てしないので、気になる問題だけいくつか選んで見た)

NeetCodeだけでなく書籍でも初っ端からTabulation(bottom up)する解説もあるけど、個人的にはStriverさんの解説みたくまず再帰をしっかり書いて、それをメモ化(top down)して、Tabulationする、という流れで考えた方が分かりやすかった。

ということで今回は、練習も兼ねてなるべく再帰→メモ化→Tabulationの3つを書いてみようと思う。(後半完全にバテてTabulationまでできてないの結構あります。今後復習のタイミングで気が向いたら追加します)

114. Climbing Stairs

Problem

You are given an integer n representing the number of steps to reach the top of a staircase. You can climb with either 1 or 2 steps at a time.

Return the number of distinct ways to climb to the top of the staircase.

Example 1:

Input: n = 2

Output: 2

Copy

Explanation:

1. 1 + 1 = 2
2. 2 = 2

Example 2:

Input: n = 3

Output: 3

Copy

Explanation:

1. 1 + 1 + 1 = 3
2. 1 + 2 = 3
3. 2 + 1 = 3

Constraints:

• 1 <= n <= 30

Solution

再帰 O(2^N)

class Solution:
    def climbStairs(self, n: int) -> int:
        
        def dfs(i: int) -> int:
            if i == 0:
                # 0段目に辿り着くための道は1つだけ
                return 1
            
            if i == 1:
                # 1段目に辿り着くための道は1つだけ
                return 1
            
            return dfs(i-1) + dfs(i-2)
        
        return dfs(n)

メモ化 (Top Down) O(N)

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = {} # i -> ways
        # 0, 1段目に辿り着くための道は1つだけ
        dp[0] = 1
        dp[1] = 1
        
        def dfs(i: int) -> int:
            if i in dp:
                return dp[i]

            dp[i] = dfs(i-1) + dfs(i-2)
            return dp[i]
        
        return dfs(n)

Tabulation (Bottom Up) O(N)

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = {} # i -> ways
        # 0, 1段目に辿り着くための道は1つだけ
        dp[0] = 1
        dp[1] = 1
        
        for i in range(2, n+1):
            dp[i] = dp[i-2] + dp[i-1]
        
        return dp[n]

115. Min Cost Climbing Stairs

Problem

You are given an array of integers cost where cost[i] is the cost of taking a step from the ith floor of a staircase. After paying the cost, you can step to either the (i + 1)th floor or the (i + 2)th floor.

You may choose to start at the index 0 or the index 1 floor.

Return the minimum cost to reach the top of the staircase, i.e. just past the last index in cost.

Example 1:

Input: cost = [1,2,3]

Output: 2

Copy

Explanation: We can start at index = 1 and pay the cost of cost[1] = 2 and take two steps to reach the top. The total cost is 2.

Example 2:

Input: cost = [1,2,1,2,1,1,1]

Output: 4

Copy

Explanation: Start at index = 0.

• Pay the cost of cost[0] = 1 and take two steps to reach index = 2.
• Pay the cost of cost[2] = 1 and take two steps to reach index = 4.
• Pay the cost of cost[4] = 1 and take two steps to reach index = 6.
• Pay the cost of cost[6] = 1 and take one step to reach the top.
• The total cost is 4.

Constraints:

• 2 <= cost.length <= 100
• 0 <= cost[i] <= 100

Solution

再帰 O(2^N)

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        
        def dfs(i: int) -> int:
            if i == 0 or i == 1:
                # 0,1はスタート地点なのでコストは0
                return 0
            
            # 2段下から来るパターン
            minus_two = dfs(i-2) + cost[i-2]

            # 1段下から来るパターン
            minus_one = dfs(i-1) + cost[i-1]

            # この段に辿り着く最小コスト
            res = min(minus_two, minus_one)

            return res

        # 最後のindexを通り過ぎたindexが階段の上
        return dfs(len(cost))

メモ化 (Top Down) O(N)

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = {} # index -> min cost
        dp[0] = dp[1] = 0
        
        def dfs(i: int) -> int:
            if i in dp:
                return dp[i]
            
            # 2段下から来るパターン
            minus_two = dfs(i-2) + cost[i-2]

            # 1段下から来るパターン
            minus_one = dfs(i-1) + cost[i-1]

            # この段に辿り着く最小コスト
            dp[i] = min(minus_two, minus_one)
            return dp[i]

        # 最後のindexを通り過ぎたindexが階段の上
        return dfs(len(cost))

Tabulation (Bottom Up) O(N)

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = {} # index -> min cost
        dp[0] = dp[1] = 0

        for i in range(2, len(cost)+1):
            # 2段下から来るパターン
            minus_two = dp[i-2] + cost[i-2]

            # 1段下から来るパターン
            minus_one = dp[i-1] + cost[i-1]

            dp[i] = min(minus_two, minus_one)
        
        # 最後のindexを通り過ぎたindexが階段の上
        return dp[len(cost)]

116. House Robber

Problem

You are given an integer array nums where nums[i] represents the amount of money the ith house has. The houses are arranged in a straight line, i.e. the ith house is the neighbor of the (i-1)th and (i+1)th house.

You are planning to rob money from the houses, but you cannot rob two adjacent houses because the security system will automatically alert the police if two adjacent houses were both broken into.

Return the maximum amount of money you can rob without alerting the police.

Example 1:

Input: nums = [1,1,3,3]

Output: 4

Copy

Explanation: nums[0] + nums[2] = 1 + 3 = 4.

Example 2:

Input: nums = [2,9,8,3,6]

Output: 16

Copy

Explanation: nums[0] + nums[2] + nums[4] = 2 + 8 + 6 = 16.

Constraints:

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

Solution

再帰 O(2^N)

class Solution:
    def rob(self, nums: List[int]) -> int:
        def dfs(i: int) -> int:
            if i == 0:
                # index = 0の時までの最大の利益は、
                # index = 0の家から盗んだ時
                return nums[0]
            
            if i == 1:
                return max(nums[0], nums[1])
            
            # pick(現在のindexの家を盗む時)
            pick = nums[i] + dfs(i-2)

            # not pick(現在のindexの家を盗まない時)
            not_pick = dfs(i-1)

            res = max(pick, not_pick)
            return res
        
        return dfs(len(nums)-1)

メモ化 (Top Down) O(N)

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
            
        dp = {} # index -> max profit
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        def dfs(i: int) -> int:
            if i in dp:
                return dp[i]
            
            # pick(現在のindexの家を盗む時)
            pick = nums[i] + dfs(i-2)

            # not pick(現在のindexの家を盗まない時)
            not_pick = dfs(i-1)

            dp[i] = max(pick, not_pick)
            return dp[i]
        
        return dfs(len(nums)-1)

Tabulation (Bottom Up) O(N)

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        dp = {} # index -> max profit
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2, len(nums)):
            # pick(現在のindexの家を盗む時)
            pick = nums[i] + dp[i-2]

            # not pick(現在のindexの家を盗まない時)
            not_pick = dp[i-1]

            dp[i] = max(pick, not_pick)
        
        return dp[len(nums)-1]

117. House Robber II

Problem

You are given an integer array nums where nums[i] represents the amount of money the ith house has. The houses are arranged in a straight line, i.e. the ith house is the neighbor of the (i-1)th and (i+1)th house.

You are planning to rob money from the houses, but you cannot rob two adjacent houses because the security system will automatically alert the police if two adjacent houses were both broken into.

Return the maximum amount of money you can rob without alerting the police.

Example 1:

Input: nums = [1,1,3,3]

Output: 4

Copy

Explanation: nums[0] + nums[2] = 1 + 3 = 4.

Example 2:

Input: nums = [2,9,8,3,6]

Output: 16

Copy

Explanation: nums[0] + nums[2] + nums[4] = 2 + 8 + 6 = 16.

Constraints:

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

Solution

再帰 O(2^N)

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        def rob_one(tmp_nums: List[int]) -> int:
            if len(tmp_nums) == 1:
                return tmp_nums[0]
            
            def dfs(i: int) -> int:
                if i == 0:
                    return tmp_nums[0]
                
                if i == 1:
                    return max(tmp_nums[0], tmp_nums[1])
                
                pick = tmp_nums[i] + dfs(i-2)
                not_pick = dfs(i-1)
                res = max(pick, not_pick)
                return res
            
            return dfs(len(tmp_nums)-1)
        
        without_first = rob_one(nums[1:])
        without_last = rob_one(nums[:-1])
        return max(without_first, without_last)

メモ化 (Top Down) O(N)

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        def rob_one(tmp_nums: List[int]) -> int:
            if len(tmp_nums) == 1:
                return tmp_nums[0]

            dp = {} # index -> max profit
            dp[0] = tmp_nums[0]
            dp[1] = max(tmp_nums[0], tmp_nums[1])
            
            def dfs(i: int) -> int:
                if i in dp:
                    return dp[i]
                
                pick = tmp_nums[i] + dfs(i-2)
                not_pick = dfs(i-1)
                dp[i] = max(pick, not_pick)
                return dp[i]
            
            return dfs(len(tmp_nums)-1)
        
        without_first = rob_one(nums[1:])
        without_last = rob_one(nums[:-1])
        return max(without_first, without_last)

Tabulation (Bottom Up) O(N)

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        def rob_one(tmp_nums: List[int]) -> int:
            if len(tmp_nums) == 1:
                return tmp_nums[0]

            dp = {} # index -> max profit
            dp[0] = tmp_nums[0]
            dp[1] = max(tmp_nums[0], tmp_nums[1])

            for i in range(2, len(tmp_nums)):
                pick = tmp_nums[i] + dp[i-2]
                not_pick = dp[i-1]
                dp[i] = max(pick, not_pick)
            
            return dp[len(tmp_nums)-1]
        
        without_first = rob_one(nums[1:])
        without_last = rob_one(nums[:-1])
        return max(without_first, without_last)

118. Longest Palindromic Substring

Problem

Given a string s, return the longest substring of s that is a palindrome.

A palindrome is a string that reads the same forward and backward.

If there are multiple palindromic substrings that have the same length, return any one of them.

Example 1:

Input: s = "ababd"

Output: "bab"

Copy

Explanation: Both "aba" and "bab" are valid answers.

Example 2:

Input: s = "abbc"

Output: "bb"

Copy

Constraints:

• 1 <= s.length <= 1000
• s contains only digits and English letters.

Solution

再帰 O(N^3)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        longest = ''
        
        def dfs(i: int, j: int) -> bool:
            nonlocal longest
            if i == j:
                # 1文字の場合
                if 1 > len(longest):
                    longest = s[i]
                return True
            
            if i + 1 == j:
                # 2文字の場合
                # 同じ文字だったらTrueを返す
                # i は j より常に左にある
                if s[i] == s[j] and 2 > len(longest):
                    longest = s[i:j+1]
                return s[i] == s[j]
            
            # 3文字以上の場合
            res = dfs(i+1, j-1) and s[i] == s[j]
            if res and j - i + 1 > len(longest):
                longest = s[i:j+1]
            return res
        
        for i in range(len(s)):
            for j in range(i, len(s)):
                dfs(i, j)
        return longest

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

class Solution:
    def longestPalindrome(self, s: str) -> str:
        longest = ''
        # (i,j) -> int (-1, 0, 1)で表現
        # 本当はFalse/Trueでいいが、チェック済みの場合のみメモから返したいので
        dp = [[-1] * len(s) for _ in range(len(s))]

        # iとjが同じ、つまり１文字の場合は常に回文
        for i in range(len(s)):
            dp[i][i] = 1
            longest = s[i]
        
        # 2文字の場合、同じ文字だったらTrue
        for i in range(len(s)-1):        
            if s[i] == s[i+1]:
                dp[i][i+1] = 1
                longest = s[i:i+2]
            else:
                # 違う文字だったら0
                dp[i][i+1] = 0
        
        def dfs(i: int, j: int) -> int:
            nonlocal longest
            if dp[i][j] != -1:
                return dp[i][j]
            
            if i > j:
                return 0
            
            # 3文字以上の場合
            res = dfs(i+1, j-1) == 1 and s[i] == s[j]
            if res and j - i + 1 > len(longest):
                longest = s[i:j+1]
            dp[i][j] = 1 if res else 0
            return dp[i][j]
        
        for i in range(len(s)):
            for j in range(i, len(s)):
                dfs(i, j)
        return longest

Tabulation (Bottom Up) O(N^2)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        longest = ''
        # (i,j) -> int (-1, 0, 1)で表現
        dp = [[False] * len(s) for _ in range(len(s))]

        # iとjが同じ、つまり１文字の場合は常に回文
        for i in range(len(s)):
            dp[i][i] = True
            longest = s[i]
        
        # 2文字の場合、同じ文字だったらTrue
        for i in range(len(s)-1):        
            if s[i] == s[i+1]:
                dp[i][i+1] = True
                longest = s[i:i+2]
        
        # 3文字以上の場合
        for j in range(2, len(s)):
            for i in range(len(s)-1):
                if s[i] == s[j] and dp[i+1][j-1]:
                    dp[i][j] = True
                    if (j - i + 1) > len(longest):
                        longest = s[i:j+1]

        return longest

別解 O(N^2)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        longest = ''

        def palin(l: int, r: int) -> None:
            nonlocal longest
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if r - l + 1 > len(longest):
                    longest = s[l:r+1]
                l -= 1
                r += 1
        
        # odd case
        for i in range(len(s)):
            palin(i, i)
        
        # even case
        for i in range(len(s)-1):
            palin(i, i+1)
        
        return longest

119. Longest Palindromic Substring

Problem

Given a string s, return the longest substring of s that is a palindrome.

A palindrome is a string that reads the same forward and backward.

If there are multiple palindromic substrings that have the same length, return any one of them.

Example 1:

Input: s = "ababd"

Output: "bab"

Copy

Explanation: Both "aba" and "bab" are valid answers.

Example 2:

Input: s = "abbc"

Output: "bb"

Copy

Constraints:

• 1 <= s.length <= 1000
• s contains only digits and English letters.

Solution

O(N^2)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        longest = ''
        
        def dfs(i: int, j: int) -> bool:
            nonlocal longest
            if i == j:
                # 1文字の場合
                if 1 > len(longest):
                    longest = s[i]
                return True
            
            if i + 1 == j:
                # 2文字の場合
                # 同じ文字だったらTrueを返す
                # i は j より常に左にある
                if s[i] == s[j] and 2 > len(longest):
                    longest = s[i:j+1]
                return s[i] == s[j]
            
            # 3文字以上の場合
            res = dfs(i+1, j-1) and s[i] == s[j]
            if res and j - i + 1 > len(longest):
                longest = s[i:j+1]
            return res
        
        for i in range(len(s)):
            for j in range(i, len(s)):
                dfs(i, j)
        return longest

120. Decode Ways

Problem

A string consisting of uppercase english characters can be encoded to a number using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

Copy

To decode a message, digits must be grouped and then mapped back into letters using the reverse of the mapping above. There may be multiple ways to decode a message. For example, "1012" can be mapped into:

• "JAB" with the grouping (10 1 2)
• "JL" with the grouping (10 12)

The grouping (1 01 2) is invalid because 01 cannot be mapped into a letter since it contains a leading zero.

Given a string s containing only digits, return the number of ways to decode it. You can assume that the answer fits in a 32-bit integer.

Example 1:

Input: s = "12"

Output: 2

Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Copy

Example 2:

Input: s = "01"

Output: 0

Copy

Explanation: "01" cannot be decoded because "01" cannot be mapped into a letter.

Constraints:

• 1 <= s.length <= 100
• s consists of digits

Solution

再帰 O(2^N)

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s or s[0] == '0':
            return 0
        
        def dfs(i: int) -> int:
            if i == 0:
                # s[:i] までの文字をデコードする場合
                # s[0] == '0' のパターンは既に排除している
                # 空文字をデコードする場合は1つと考える？
                # 2文字一緒にデコードする時にこの1を使う
                return 1
            
            if i == 1:
                # s[:i] なので、1文字の場合
                # s[0] == '0'のパターンは排除済みなので一律1を返す
                return 1
            
            # 当該文字を１文字としてデコードする場合
            # 例えば '12' の時、dfs(2) で 2 を１文字として数える場合の数は
            # dfs(1) の結果と等しい (1,2をそれぞれ1文字として数える)
            as_one = 0
            if s[i-1] != '0':
                as_one = dfs(i-1)

            as_two = 0
            if s[i-2] == '1' or (s[i-2] == '2' and s[i-1] in '0123456'):
                as_two = dfs(i-2)
            
            return as_one + as_two
        
        return dfs(len(s))

メモ化 (Top Down) O(N)

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s or s[0] == '0':
            return 0

        dp = [-1] * (len(s) + 1) # index -> pattern
        dp[0] = 1
        dp[1] = 1
        
        def dfs(i: int) -> int:
            if dp[i] != -1:
                return dp[i]
            
            as_one = 0
            if s[i-1] != '0':
                as_one = dfs(i-1)

            as_two = 0
            if s[i-2] == '1' or (s[i-2] == '2' and s[i-1] in '0123456'):
                as_two = dfs(i-2)
            
            dp[i] = as_one + as_two
            return dp[i]
        
        return dfs(len(s))

Tabulation (Bottom Up) O(N)

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s or s[0] == '0':
            return 0

        dp = [0] * (len(s) + 1) # index -> pattern
        dp[0] = 1
        dp[1] = 1

        for i in range(2, len(s)+1):
            if s[i-1] != '0':
                dp[i] += dp[i-1]
            if s[i-2] == '1' or (s[i-2] == '2' and s[i-1] in '0123456'):
                dp[i] += dp[i-2]

        return dp[len(s)]

121. Coin Change

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 fewest number of coins that you need to make up the exact target amount. If it is impossible to make up the amount, return -1.

You may assume that you have an unlimited number of each coin.

Example 1:

Input: coins = [1,5,10], amount = 12

Output: 3

Copy

Explanation: 12 = 10 + 1 + 1. Note that we do not have to use every kind coin available.

Example 2:

Input: coins = [2], amount = 3

Output: -1

Copy

Explanation: The amount of 3 cannot be made up with coins of 2.

Example 3:

Input: coins = [1], amount = 0

Output: 0

Copy

Explanation: Choosing 0 coins is a valid way to make up 0.

Constraints:

• 1 <= coins.length <= 10
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 1000

Solution

再帰 O(S^N) (Sはamountの値、NはCoinの数)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        
        def dfs(a: int) -> int:
            if a == 0:
                # amount == 0は0枚のコインでできる
                return 0
            
            # 使うコインの枚数の最小値を初期化
            res = math.inf
            for c in coins:
                if a - c >= 0:
                    res = min(res, 1 + dfs(a-c))
            
            return res
        
        res = dfs(amount)
        return res if res != math.inf else -1

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

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [math.inf] * (amount + 1)
        dp[0] = 0
        
        def dfs(a: int) -> int:
            if dp[a] != math.inf:
                return dp[a]
            
            # 使うコインの枚数の最小値を初期化
            res = math.inf
            for c in coins:
                if a - c >= 0:
                    res = min(res, 1 + dfs(a-c))
            
            dp[a] = res
            return dp[a]
        
        res = dfs(amount)
        return res if res != math.inf else -1

Tabulation (Bottom Up) O(S * N)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [math.inf] * (amount + 1)
        dp[0] = 0

        for i in range(amount + 1):
            for c in coins:
                if i - c >= 0:
                    dp[i] = min(dp[i], dp[i-c] + 1)
        
        return dp[amount] if dp[amount] != math.inf else -1

122. Maximum Product Subarray

Problem

Given an integer array nums, find a subarray that has the largest product within the array and return it.

A subarray is a contiguous non-empty sequence of elements within an array.

You can assume the output will fit into a 32-bit integer.

Example 1:

Input: nums = [1,2,-3,4]

Output: 4

Copy

Example 2:

Input: nums = [-2,-1]

Output: 2

Copy

Constraints:

• 1 <= nums.length <= 1000
• -10 <= nums[i] <= 10

Solution

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        max_sofar = nums[0]
        min_sofar = nums[0]
        global_max = nums[0]

        for num in nums[1:]:
            if num < 0:
                max_sofar, min_sofar = min_sofar, max_sofar
            
            max_sofar = max(num, max_sofar * num)
            min_sofar = min(num, min_sofar * num)

            global_max = max(global_max, max_sofar)
        
        return global_max

123. Word Break

Problem

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of dictionary words.

You are allowed to reuse words in the dictionary an unlimited number of times. You may assume all dictionary words are unique.

Example 1:

Input: s = "neetcode", wordDict = ["neet","code"]

Output: true

Copy

Explanation: Return true because "neetcode" can be split into "neet" and "code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen","ape"]

Output: true

Copy

Explanation: Return true because "applepenapple" can be split into "apple", "pen" and "apple". Notice that we can reuse words and also not use all the words.

Example 3:

Input: s = "catsincars", wordDict = ["cats","cat","sin","in","car"]

Output: false

Copy

Constraints:

• 1 <= s.length <= 200
• 1 <= wordDict.length <= 100
• 1 <= wordDict[i].length <= 20
• s and wordDict[i] consist of only lowercase English letters.

Solution

再帰 O(2^N K L) (Kは単語の数、Nはsの長さ、Lは単語の最大長)

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        
        def dfs(i: int) -> bool:
            if i == 0:
                # 空文字はwordDictの文字を使わずとも構成できる
                return True
            
            res = False
            for word in wordDict:
                if i - len(word) >= 0 and s[i-len(word):i] == word:
                    if dfs(i-len(word)):
                        res = True
            return res
        
        return dfs(len(s))

メモ化 (Top Down) O(N K L)

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = {} # index -> bool
        dp[0] = True
        
        def dfs(i: int) -> bool:
            if i in dp:
                return dp[i]
            
            res = False
            for word in wordDict:
                if i - len(word) >= 0 and s[i-len(word):i] == word:
                    if dfs(i-len(word)):
                        res = True
            
            dp[i] = res
            return dp[i]
        
        return dfs(len(s))

Tabulation (Bottom Up) O(N K L)

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * (len(s) + 1)
        dp[0] = True
        for i in range(1, len(s)+1):
            for word in wordDict:
                if i - len(word) >= 0 and s[i-len(word):i] == word:
                    dp[i] = dp[i] or dp[i - len(word)]
        return dp[len(s)]

124. Longest Increasing Subsequence

Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence.

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".

Example 1:

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

Output: 4

Copy

Explanation: The longest increasing subsequence is [1,2,3,7], which has a length of 4.

Example 2:

Input: nums = [0,3,1,3,2,3]

Output: 4

Copy

Constraints:

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

Solution

再帰 O(2^N)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        def dfs(i: int, last_val: int) -> int:
            if i == len(nums):
                # numsのindexを超えたらおしまい
                return 0
            
            pick = 0
            if nums[i] > last_val:
                # 前の数よりも大きければ足すことができる
                pick = 1 + dfs(i+1, nums[i])
            # 前の数よりも大きかろうが小さかろうが足さないことはできる
            not_pick = dfs(i+1, last_val)
            return max(pick, not_pick)

        return dfs(0, -math.inf)

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

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = {} # (i, last_val) -> max sequence
        
        def dfs(i: int, last_val: int) -> int:
            if i == len(nums):
                # numsのindexを超えたらおしまい
                return 0
            
            if (i, last_val) in dp:
                return dp[(i, last_val)]

            pick = 0
            if nums[i] > last_val:
                # 前の数よりも大きければ足すことができる
                pick = 1 + dfs(i+1, nums[i])
            # 前の数よりも大きかろうが小さかろうが足さないことはできる
            not_pick = dfs(i+1, last_val)

            dp[(i, last_val)] = max(pick, not_pick)
            return dp[(i, last_val)]

        return dfs(0, -math.inf)

Tabulation (Bottom Up) O(N^2)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # dp[i]は、nums[0]からnums[i]までの最長増加部分列の長さ
        dp = [1] * len(nums)

        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], 1 + dp[j])
                
        return max(dp)

125. Partition Equal Subset Sum

Problem

You are given an array of positive integers nums.

Return true if you can partition the array into two subsets, subset1 and subset2 where sum(subset1) == sum(subset2). Otherwise, return false.

Example 1:

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

Output: true

Copy

Explanation: The array can be partitioned as [1, 4] and [2, 3].

Example 2:

Input: nums = [1,2,3,4,5]

Output: false

Copy

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 50

Solution

再帰 O(2^N)

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False
        
        half = total // 2

        def dfs(i: int, subtotal: int) -> bool:
            if subtotal == half:
                return True
            
            if subtotal > half or i == len(nums):
                return False
            
            # pick
            pick = dfs(i+1, subtotal + nums[i])

            # not pick
            not_pick = dfs(i+1, subtotal)

            return pick or not_pick
        
        return dfs(0, 0)

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

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False
        
        half = total // 2

        dp = {} #(i, subtotal) -> bool

        def dfs(i: int, subtotal: int) -> bool:
            if subtotal == half:
                return True
            
            if subtotal > half or i == len(nums):
                return False
            
            if (i, subtotal) in dp:
                return dp[(i, subtotal)]
            
            # pick
            pick = dfs(i+1, subtotal + nums[i])

            # not pick
            not_pick = dfs(i+1, subtotal)

            dp[(i, subtotal)] = pick or not_pick
            return dp[(i, subtotal)]
        
        return dfs(0, 0)

Tabulation (Bottom Up) O(N * half)

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False
        
        half = total // 2

        dp = [[False] * (half + 1) for _ in range(len(nums) + 1)]
        for i in range(len(nums) + 1):
            dp[i][half] = True
        
        for i in range(len(nums)-1, -1, -1):
            for j in range(half-1, -1, -1):
                pick = False
                if j + nums[i] <= half:
                    pick = dp[i+1][j + nums[i]]
                not_pick = dp[i+1][j]
                dp[i][j] = pick or not_pick
        
        return dp[0][0]