6.9 练习

# 6.9 练习

## 基础难度

### [213. House Robber II](https://leetcode.com/problems/house-robber-ii/)

强盗抢劫题目的 follow-up，如何处理环形数组呢？
```py
class Solution:
    def myrob(self, nums):
        n = len(nums)
        if n < 2:
            return max(nums)
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2,n):
            dp[i] = max(dp[i-2] + nums[i], dp[i-1])
        return dp[-1]
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return max(nums)
        case1 = self.myrob(nums[:-1])
        case2 = self.myrob(nums[1:])
        return max(case1,case2)
```
---
### [53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)

经典的一维动态规划题目，试着把一维空间优化为常量吧。

dp[i] 表示以 nums[i] 结尾的最大子数组和
```py
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        dp = [0] * n
        dp[0] = nums[0]
        for i in range(1, n):
            dp[i] = max(dp[i-1], 0) + nums[i]
        return max(dp)
```
---

### [343. Integer Break](https://leetcode.com/problems/integer-break/)

分割类型题，先尝试用动态规划求解，再思考是否有更简单的解法。
```py
class Solution:
    def integerBreak(self, n: int) -> int:
        # n = 2, max = 1
        # n = 3, max = 2 = max(1*2, 2*1, 1*1*1)
        # n = 4, max = 4 = max(1*3, 2*2, 3*1, 1*1*1*1)
        dp = [-1] * (n + 1)
        dp[1] = 1
        dp[2] = 1
        for i in range(3, n + 1):
            for j in range(1, i):
                dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
        return dp[n]
```
---

### [583. Delete Operation for Two Strings](https://leetcode.com/problems/delete-operation-for-two-strings/)

dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。
```py
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[inf] * (n+1) for _ in range(m+1)]
        dp[0][0] = 0
        for i in range(1,m+1):
            dp[i][0] = i
        for j in range(1,n+1):
            dp[0][j] = j
        for i in range(1, m+1):
            for j in range(1,n+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] +1, dp[i-1][j-1]+2)
        return dp[m][n]
```
---

## 进阶难度

### [646. Maximum Length of Pair Chain](https://leetcode.com/problems/maximum-length-of-pair-chain/)

最长递增子序列的变种题，同样的，尝试用二分进行加速。

---

### [10. Regular Expression Matching](https://leetcode.com/problems/regular-expression-matching/)

正则表达式匹配，非常考验耐心。需要根据正则表达式的不同情况，即字符、星号，点号等，分情况讨论。

---

### [376. Wiggle Subsequence](https://leetcode.com/problems/wiggle-subsequence/)

最长摆动子序列，通项公式比较特殊，需要仔细思考。

---

### [494. Target Sum](https://leetcode.com/problems/target-sum/)

如果告诉你这道题是 0-1 背包，你是否会有一些思路？

---

### [714. Best Time to Buy and Sell Stock with Transaction Fee](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)

建立状态机，股票交易类问题就会迎刃而解。