0.15 动态规划

[70. 爬楼梯](https://leetcode.cn/problems/climbing-stairs/?envType=study-plan-v2&envId=top-100-liked)
```python
class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0] * (n+1)
        if n < 2:
            return 1
        dp[0] = 1
        dp[1] = 1
        for i in range(2,n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]
```
[118. 杨辉三角](https://leetcode.cn/problems/pascals-triangle/?envType=study-plan-v2&envId=top-100-liked)
```python
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        dp = [[1] * (i+1) for i in range(numRows)]
        for i in range(numRows):
            for j in range(1,i):
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
        return dp
```
[198. 打家劫舍](https://leetcode.cn/problems/house-robber/?envType=study-plan-v2&envId=top-100-liked)
```python
class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * n
        if n < 2:
            return max(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2,n):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i])
        return dp[-1]
```
[279. 完全平方数](https://leetcode.cn/problems/perfect-squares/?envType=study-plan-v2&envId=top-100-liked)
```python
import math
class Solution:
    def numSquares(self, n: int) -> int:
        dp = [inf] * (n+1)
        dp[0] = 0
        dp[1] = 1
        for i in range(2,n+1):
            for j in range(1,isqrt(i) + 1):
                dp[i] = min(dp[i], dp[i-j*j] + 1)
        return dp[n]
```
[322. 零钱兑换](https://leetcode.cn/problems/coin-change/?envType=study-plan-v2&envId=top-100-liked)
```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [inf] * (amount+1)
        dp[0] = 0
        for i in range(1,amount+1):
            for coin in coins:
                if coin <= i:
                    dp[i] = min(dp[i], dp[i-coin] + 1)
        return dp[amount] if dp[amount] != inf else -1
```
[139. 单词拆分](https://leetcode.cn/problems/word-break/?envType=study-plan-v2&envId=top-100-liked)
```python
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        dp = [False] * (n+1)
        dp[0] = True
        for i in range(1, n+1):
            for j in range(i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break
        return dp[n]
```
[300. 最长递增子序列](https://leetcode.cn/problems/longest-increasing-subsequence/?envType=study-plan-v2&envId=top-100-liked)
$$O(N^2)$$
```python
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j]+1)
        return max(dp)
```
$$O(NlogN)$$
```python
class Solution:
    def findfirst(self, nums, target):
        n = len(nums)
        left, right = 0, n-1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left

def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        res = []
        for num in nums:
            i = self.findfirst(res, num)
            if i == len(res):
                res.append(num)
            else:
                res[i] = num
        return len(res)
```
[152. 乘积最大子数组](https://leetcode.cn/problems/maximum-product-subarray/?envType=study-plan-v2&envId=top-100-liked)
```python
class Solution:
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        min_dp = [inf] * n
        max_dp = [-inf] * n
        res = min_dp[0] = max_dp[0] = nums[0]
        for i in range(1, n):
            candidate = (nums[i], min_dp[i - 1] * nums[i], max_dp[i - 1] * nums[i])
            min_dp[i] = min(candidate)
            max_dp[i] = max(candidate)
            res = max(res, max_dp[i])
        return res
```
[416. 分割等和子集](https://leetcode.cn/problems/partition-equal-subset-sum/?envType=study-plan-v2&envId=top-100-liked)
```python
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 == 1:
            return False
        target = total // 2

@cache
        def dfs(i, cur_sum):
            if cur_sum == target:
                return True
            if i == len(nums) or cur_sum > target:
                return False
            return dfs(i + 1, cur_sum) or dfs(i + 1, cur_sum + nums[i])

return dfs(0, 0)
```
```python
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 == 1:
            return False
        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True
        for num in nums:
            for i in range(target, num - 1, -1):
                if dp[i - num]:
                    dp[i] = True
            if dp[target]:
                return True
        return dp[target]
```
[32. 最长有效括号](https://leetcode.cn/problems/longest-valid-parentheses/?envType=study-plan-v2&envId=top-100-liked)
```python
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        res = 0
        for i in range(len(s)):
            if s[i] == "(":
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    res = max(res, i - stack[-1])
        return res
```
动态规划
```
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0
        dp = [0] * n
        res = 0
        for i in range(1, n):
            if s[i] == ")":
                if s[i - 1] == "(":
                    dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
                elif i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == "(":
                    dp[i] = (
                        dp[i - 1]
                        + 2
                        + (dp[i - dp[i - 1] - 2] if (i - dp[i - 1]) >= 2 else 0)
                    )
                res = max(res, dp[i])
        return res

```