# 1-D Dynamic Programming (12)

> 紀錄 NeetCode-150 與 LeetCode 的解題想法、刷題過程與錯誤，以 Python 或 C++ 兩種語言為主
>
> 其他 NeetCode-150 或 LeetCode 的主題請見 [Here](https://hackmd.io/-ovTFlzLRWaSgzDGhbSwsA)

<!-- 常用色碼紀錄
Easy: <font color="#00ad5f">**Easy**</font>
Medium: <font color="#ffbb00">**Medium**</font>
Hard: <font color="#ee2f56">**Hard**</font>
-->

## 1. Climbing Stairs
<font color="#00ad5f">**Easy**</font>

> 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

Explanation:

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

### Example 2:

Input: n = 3

Output: 3

Explanation:

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

### Constraints

* 1 <= n <= 30

### Recommended complexity

* Time complexity: $O(n)$
* Space complexity: $O(n)$
* `n` is the number o f steps

### Solution

#### 1. Recursion ver.

# Recursive ver.
class Solution:
    def climbStairs(self, n: int) -> int:
        # boundary condition
        M = [-1] * (n + 1)
        M[0], M[1] = 1, 1
        
        def fin(n):
            if M[n] == -1:
                M[n] = fin(n-1) + fin(n-2)
            return M[n]
        
        return fin(n)

#### 2. Iteration ver.

# Iteration ver.
class Solution:
    def climbStairs(self, n: int) -> int:
        # boundary condition
        M = [-1] * (n + 1)
        M[0], M[1] = 1, 1

        # bottom-up
        for i in range(n+1):
            if M[i] == -1:
                M[i] = M[i-1] + M[i-2]
        return M[n]

## 2. Min Cost Climbing Stairs
<font color="#00ad5f">**Easy**</font>

> 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

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

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`

### Recommended complexity

* Time complexity: As good or better than $O(n)$
* Space complexity: As good or better than $O(n)$

### Solution

#### 1. Recursion ver.

依據 memory 建構方向不同，top-down 的遞迴有兩種實現方式。

(1) `M[i]` 表示到第 i 階的最小成本
類似費式數列的建構方式，樹的根節點表示頂端階梯的位置，往下延伸進行遞迴的計算。Base condition 是當 i = 0 或 i = 1 時 M[0] 與 M[1] 皆為 0，表示從 index 0 與 index 1 出發的最小成本。

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost) + 1
        M = [-1] * n

        def dp(n):
            if n == 0 or n == 1:
                M[n] = 0
            if M[n] == -1:
                M[n] = min(dp(n-1) + cost[n-1],
                           dp(n-2) + cost[n-2])
            return M[n]
        return dp(n-1)

(2) M[i] 表示從第 i 階出發到終點的最小成本
比較符合走樓梯的方式。Base condition 是當 i 超過階梯長度時表示抵達終點，回傳 0(終點到終點的成本)

# Recursive ver. 2
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        M = [-1] * len(cost)

        def dp(i):
            if i >= len(cost):
                return 0

            if M[i] == -1:
                M[i] = cost[i] + min(dp(i+1), dp(i+2))
            
            return M[i]
        
        return min(dp(0), dp(1))

#### 2. Iteration ver.
從起點開始填表格，M[i] 表示到第 i 階的最小成本，因此 base condition 同樣是 i = 0 或 i = 1 時 M[0] 與 M[1] 皆為 0。

# Iteration ver.
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        M = [-1] * (n + 1)

        # boundary condition
        M[0], M[1] = 0, 0

        for i in range(2, n+1):
            M[i] = min(cost[i-1] + M[i-1],
                       cost[i-2] + M[i-2])
        
        return M[n]

## 3. House Robber
<font color="#ffbb00">**Medium**</font>

> You are given an integer array `nums` where `nums[i]` represents the amount of money the `i`th house has. The houses are arranged in a straight line, i.e. the `i`th 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

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

### Exmple 2:

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

Output: 16

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

### Constraints

* `1 <= nums.length <= 100`
* `0 <= nums[i] <= 100`

### Recommended complexity

* Time complexity: as good or better than $O(n)$
* n is the number of houses
* Space complexity: as good or better than $O(n)$

### Solution

類似前一題 Min Cost Climbing Stairs，畫出搶劫路線的樹狀圖後可以更清楚每個點的行為以及遞迴關係式


對樣可以使用 recursion 與 iteration 兩種方法

#### 1. Recursion ver.

根據樹狀圖的路徑，對於每個地點可以選擇要不要搶劫:

* 搶劫該點：搶劫後往下下個地點前進，金額往上遞增 `nums[i] + dp(i+2)`
* 若不搶劫該點：往下個地點前進，金額延續前一個點 `dp(i-1)`

使用一維陣列 `M[]` 維護過程中需要重複計算的內容，`M[i]` 表示從該 `index = i` 出發的最大搶劫總金額，也就是上述兩式取最大值的結果，最後再回傳 `dp(0)`。

# Recursive ver.
class Solution:
    def rob(self, nums: List[int]) -> int:
        M = [-1] * len(nums)

        def dp(i):
            if i >= len(nums):
                return 0
            
            # rob nums[i] or not
            if M[i] == -1:
                M[i] = max(nums[i] + dp(i+2), dp(i+1))
            return M[i]
        return dp(0)              

#### 2. Iteration ver.

同樣與前一題 Min Cost Climbing Stairs 的 iteration ver. 類似，從頭開始建立表格。對每個點 `index = i` 同樣可以選擇要不要搶劫該點

* 搶劫該點: 該點金額以及往前找上上個地點的總金額 `num[i] + M[i-2]`
* 不搶劫該點: 繼承上個地點的總金額 `M[i-1]`

使用一維陣列 `M[]` 維護填表過程，`M[i]` 表示從該 `index = i` 從起點開始到 `index = i` 的最大搶劫總金額，也就是上述兩式取最大值的結果，最後再回傳 `M[-1]`

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

        # settup table and boundary condition
        M = [-1] * len(nums)
        M[0] = nums[0]
        M[1] = max(nums[1] + 0, nums[0]) # rob nums[i] or not 

        for i in range(2, len(nums)):
            M[i] = max(nums[i] + M[i-2], M[i-1]) # rob nums[i] or not
        
        return M[-1]

## 4. House Robber II
<font color="#ffbb00">**Medium**</font>

> You are given an integer array `nums` where `nums[i]` represents the amount of money the `i`th house has. The houses are arranged in a circle, i.e. the first house and the last house are neighbors.
>
> 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 = [3,4,3]

Output: 4

Explanation: You cannot rob `nums[0] + nums[2] = 6` because `nums[0]` and `nums[2]` are adjacent houses. The maximum you can rob is `nums[1] = 4`

### Example 2:

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

Output: 15

Explanation: You cannot rob `nums[0] + nums[2] + nums[4] = 16` because `nums[0]` and `nums[4]` are adjacent houses. The maximum you can rob is `nums[1] + nums[4] = 15`.

### Constraints

* `1 <= nums.length <= 100`
* `0 <= nums[i] <= 100`

### Recommended compleity

* Time complexity: as good or better than $O(n)$
* n is the number of houses
* Space complexity: as good or better than $O(n)$

### Solution

因為起點與終點必定會發生衝突，所以可以把這衝突分開討論

* 若不走起點：從 `i = 1` 出發，且可以經過終點(也可以不經過)
* 基本上與前一題一樣，只是要強制不走起點
* 若可以走起點：從 `i = 0` 出發，且不經過終點
* 需要強制設定不經過終點的條件


總結來說，類似起點不同的 Climbing Stairs 問題，可以直接把不同起點以上圖的方式分開討論。

#### 1. Recursion ver.

遞迴版本的重點在於要如何在函式內部決定現在是使用哪一種討論情況做遞迴？這個問題可以多增加一個參數解決。將遞迴函式 `dp()` 新增一個參數 `flag` 控制討論情況

* `flag = True` 表示從起點出發，但不能過終點
* 當 `flag = True` 且位在終點位置 `i = len(nums)-1` 時，因為不考慮這個點所以直接回傳此點的總金額為 `0`
* `flag = False` 表示不從起點出發，但可以過終點
* 與前一題相同，只要位置超出範圍(`i >= len(nums)`)就回傳 `0`

因為分兩種狀況討論，所以不同的是這邊要使用二維陣列 `M[2][n]` 來維護重複計算的值，且 `M[][j]` 同樣表示從該點出發到終點的總金額，最後回傳從起點或第二點出發的總金額最大值。

# Recursion ver.
class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        
        M = [[-1] * len(nums) for i in range(2)]
        
        def dp(i, flag):
            if i >= len(nums) or (flag and i == len(nums)-1):
                return 0
            
            if M[flag][i] == -1:
                M[flag][i] = max(nums[i] + dp(i+2, flag), 
                                 dp(i+1, flag))
            
            return M[flag][i]
        
        return max(dp(0, True), dp(1, False))

#### 2. Itertion ver.

迭代版本與前一題的迭代版本類似，且同樣使用一個變數 `flag` 維護現在是從哪個點出發。在設定邊界條件時也需要考慮兩種討論狀況

* 不走起點：起點為 `0` 且第二點為 `nums[1]`
* 走起點：起點第二點皆為 `nums[0]`(因為相鄰點不能走)

也是使用二維陣列 `M[2][n]` 填表格，`M[][j]` 表示的是在該討論下抵達 `index = j` 所需的最大成本。

# Iteration ver.
class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        
        M = [[-1] * len(nums) for i in range(2)]
        
        # boundary condition
        M[1][0], M[1][1] = nums[0], nums[0] # rob first
        M[0][0], M[0][1] = 0, nums[1]       # rob not first

        for flag in [True, False]:
            for i in range(2, len(nums)):
                if flag and (i == len(nums)-1):
                    M[flag][i] = max(M[flag][i-2], M[flag][i-1])
                    continue

                M[flag][i] = max(nums[i] + M[flag][i-2],
                                 M[flag][i-1])
        
        return max(M[0][-1], M[1][-1])

## 5. Longest Palindromic Substring
<font color="#ffbb00">**Medium**</font>

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

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

### Example 2:

Input: s = "abbc"

Output: "bb"

### Constraints

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

### Recommended complexity

* Time complexity: as good or better than $O(n^2)$
* n is the length of the given string
* Space complexity: $O(1)$

### Solution

> [!Note]
> 這題也可以用 two pointer 解

使用 dynamic programming 的時間/空間複雜度皆為 $O(n^2)$。但這提要使用 DP 解有幾個小技巧要注意

1. 要判斷是不是 palindrome 可以從字串中間開始往左右兩側同步檢查
* 先檢查 `s[i] == s[j]` 再檢查 `s[i-1] == s[j+1]`
* 如果是長度為 1 的子字串(`j-1=0`)直接就是 palindrome。Ex: `a`
* 如果是長度為 2 的子字串(`j-1=1`)需要檢查左右兩側是不是相同(`s[i] == s[j]`)。Ex: `aa`
* 如果是長度為 3 的子字串(`j-1=2`)需要檢查左右兩側是不是相同(`s[i] == s[j]`)。Ex: `aba`
* 如果是長度為 4 的子字串
* 檢查 `s[i] == s[j]` 之前需要先確保前一位 `s[i+1] == s[j-1]` 是回文
* 所以開始的位置 `i` 會從比較大的數字往下迭代，結束的位置 `j` 會從比較小的數字往上迭代
* 此概念就是填表格前要先確保前面的位置已經完成
2. 記憶表格可用一個二維陣列 `M[n][n]` 表示，其中 `M[i][j] = True` 表示從 `s[i]` 到 `s[j]` 的字串是 palindrome
3. 每當找到一個 palindrome 除了更新 `M[i][j]` 外，也要維護回文長度 `resLen` 與開始位置 `resIdx`

class Solution:
    def longestPalindrome(self, s: str) -> str:
        resIdx = 0
        resLen = 0
        n = len(s)

        M = [[False] * n for _ in range(n)]
        for i in range(n-1, -1, -1):
            for j in range(i, n):
                if (s[i] == s[j]) and (j - i <= 2 or M[i+1][j-1]):
                    M[i][j] = True

                    # update start idx an length
                    if resLen < (j - i + 1):
                        resLen = j - i +  1
                        resIdx = i
        return s[resIdx:resIdx + resLen]

## 6.

## 7.

## 8. Coin Change
<font color="#ffbb00">**Medium**</font>

> 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

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

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

### Example 3:

Input: coins = [1], amount = 0

Output: 0

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 <= 10000`

### Recommended complexity

* Time complexity: $O(n \codt t)$
* n is the number of coins
* t is the given amount
* Space complexity: $O(t)$

### Solution

畫出樹狀圖可更理解 DP 過程。


因為要回傳最少的硬幣數，所以需要計算所有分支所形成的硬幣組合的數量，並取所有分支的最小值，所以 DP 遞迴式為 `1 + min(dp(amt - coins[i]))`。

只有當要湊的金額(`amt`) >= 0 時才需要繼續湊硬幣/算遞迴。因為金額小於 0 是無法湊出的。此外當要湊的金額(`amt`)為 0 時不用任何硬幣，所以直接回傳 `0`。最後處理無法湊出金額的情況回傳 `-1`。

`M[i]` 表示 `amount = i` 所需的最少硬幣數

#### 1. Recursion ver.

# Recursion ver.
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0
        
        M = [-1] * (amount + 1)
        def dp(amt):
            if amt == 0:
                M[amt] = 0
                return M[amt]
            
            if M[amt] == -1:
                res = float("inf")
                for coin in coins:
                    if amt - coin >= 0:
                        res = min(res, 1 + dp(amt - coin))
            
                M[amt] = res
            
            return M[amt]
        res = dp(amount)
        return res if res != float("inf") else -1

#### 2. Iteration ver.

迭代版本的概念相同，但需要額外設定邊界條件，當金額 `amt = 0` 時，`M[amt] = 0`。

# Iteration ver.
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0
        
        # boundary condition
        M = [-1] * (amount + 1)
        M[0] = 0
        
        for amt in range(1, amount+1):
            res = float("inf")
            for coin in coins:
                if amt - coin >= 0:
                    res = min(res, M[amt - coin])
            M[amt] = res + 1
        
        return M[amount] if M[amount] != float("inf") else -1

## 9. Maximum Product Subarray
<font color="#ffbb00">**Medium**</font>

> 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

### Example 2:

Input: nums = [-2,-1]

Output: 2

### Constraints

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

### Recommended complexity

* Time complexity: $O(n)$
* Space complexity: $O(1)$

### Solution

> [!Note]
> 不算正規的 top-down/bottom-up DP 解，是 bottom-up 加上 DP 的數學歸納法概念。

考慮到原始的 array 中如果有負數，那 subarray 的乘積可能會有正負相間的情況產生

* Ex. `[-1, -2, -3]` 中的 subarray `[-1, -2]` 乘積為 `-2`
* 加入下一個元素 `-3` 後乘積為最小值 = `-6`
* Ex. `[-1, -2, 3]` 中的 subarray `[-1, -2]` 乘積為 `-2`
* 加入下一個元素 `3` 後乘積為最大值 = `6`

因為乘上下一個元素時，subarray 的乘積的符號會影響到結果的符號，最大/小值可能會被反轉。因此要同時追蹤 subarray 的最大與最小值，才能在不確定下一個元素正負的情況下得到最大乘積。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        res = -float("inf")
        currentMax, currentMin = 1, 1 # initialized

        for n in nums:
            temp = currentMax
            currentMax = max(currentMax * n, currentMin * n, n)
            currentMin = min(temp * n, currentMin * n, n)

            res = max(currentMax, res)
        
        return res

## 10. Word Break
<font color="#ffbb00">**Medium**</font>

> 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

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

### Example 2:

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

Output: true

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

### 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

這題重點在於字串的拆分(break)，要每個字元的選擇重點在於「這個字元能不能作為拆分點」。以 Example 1 為例

* `s[0] = 'n'` 不能作為拆分點，因為字典 `wordDict` 中沒有跟它對應的字串
* `s[3] = 't'` 可以作為拆分點，因為字典 `wordDict` 中的 `"neet"` 可以對應 `s[0:3]`

有兩種方式可以尋找拆分點

(1) 以字串 `s` 為主，歷遍每個字元
假設 `s[j]` 是某個拆分點，針對後續的每個位置 `s[i]` 去檢查它能不能成為拆分點。比較 `wordDict` 中有沒有與 `s[j:i]` 相同的字串

* 有，則 `s[i]` 可以成為拆分點
* 沒有，則 `s[i]` 不能成為拆分點，檢查下一個點 `s[i+1]` 與字串 `s[j:i+1]`

(2) 以字典 `wordDict` 為主，每次都歷遍 `wordDict` 中的候選字串
針對每個位置 `s[i]` 檢查它能不能作為一個拆分點。假設 `wordDict` 中的每個字串 `w`

* 若 `s[i:i+len(w)]` 的字串與 `w` 相同，表示 `s[i]` 可以作為一個拆分點。再檢查下一個位置 `s[i+len(w)]` 的子問題
* 若 `s[i:i+len(w)]` 的字串與 `w` 不同，表示 `w` 不能對應，檢查 `wordDict` 中的下一個字串

這裡採用第二種方式，樹狀圖如下。`M[i]` 表示第 `i` 個位置能不能作為拆分點。因為同一組分支可能有多個匹配的候選字串，所以當有匹配字串時要繼續遞迴，保證整條後續路徑都是可以成功拆分，才能紀錄 `M[i] = True`

<img src="https://hackmd.io/_uploads/SJ5J9l8okl.png" width=500>

#### 1. Recursion ver.
`M[i]` 表示字串從 index = i 開始能不能拆分

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        M = [-1] * len(s)

        def dp(i):
            if i == len(s):
                return True
            
            if M[i] != -1:
                return M[i]
            
            for word in wordDict:
                if ((i + len(word)) <= len(s) and
                    s[i:i+len(word)] == word):
                    if dp(i + len(word)):
                        M[i] = True
                        return M[i]
            
            M[i] = False
            return M[i]
        
        return dp(0)

#### 2. Iteration ver.

迭代版本須從字串 `s` 的尾端開始往前填表格，原因可參見 [2-D Dynamic Programming (11)](/-HXNmSFPRi62OGTwuuBezw) 中的第 2 題。

要確定 `s[i]` 能不能成為一個拆分點，需要確保他之後的字串可以完整拆分，迭代關係式為 `M[i] = M[i + len(w)]`。以 Example 3 為例，當檢查 `s[6]` (c)時匹配到了 `s[6:9]` 與 `wordDict` 中的 `"car"` 相同，表示該點可以拆分，所以理論上來說應該要設 `s[6] = True`，但因為子問題的 `s[9]` (s)是不能拆分的，所以連帶的就算 `s[6]` 可以拆分也沒用，因此要設為 `s[6] = s[9]`，即 `s[6] = False`。

`M[i]` 表示字串從 index = i 開始能不能拆分

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        M = [False] * (len(s) + 1)

        # bounary
        M[len(s)] = True # Null string can split
        for i in range(len(s) - 1, -1, -1):
            for w in wordDict:
                if (i + len(w) <= len(s) and s[i:i+len(w)] == w):
                    M[i] = M[i + len(w)]
                if M[i]: # if M[i] can split, escape this loop
                    break
        return M[0]

## 11. Longest Increasing Subsequence
<font color="#ffbb00">**Medium**</font>

> 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

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

### Constraints

* `1 <= nums.length <= 1000`
* `-1000 <= nums[i] <= 1000`

### Solution

如下的樹狀圖所示，第 i 個點的貢獻除自己之外，也取決於後面序列中的最大子序列是多少，關係式為 `M[i] = 1 + max(M[i+1], M[i+2], ...)`，因此需要從後往前建立表格。


因為題目要求的序列是遞增序列，因此 index = i 的數字對後面的子序列有無貢獻取決於他有沒有 < 後面子序列的數字

* 有(符合遞增序列)，index = i 納入後面子序列的貢獻
* 沒有(不符合遞增序列)，index = i 不納入後面子序列貢獻，從此點開始的子序列長度 = 1

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        M = [-1] * len(nums)

        # boundary
        M[n-1] = 1
        for i in range(n-2, -1, -1):
            res = 0
            for j in range(i+1, n):
                if nums[i] >= nums[j]:
                    continue
                res = max(res, M[j])
            M[i] = res + 1
        
        return max(M)

(`M[i]` 表示從 index = i 開始計算的最大子序列長度)

## 12. Partition Equal Subset Sum
<font color="#ffbb00">**Medium**</font>