算法刷题





```
22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
```

```python
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def dfs(sol: str, left: int, right: int):
            if left == 0 and right == 0:
                res.append(sol[:])
                return
            if left == right:
                dfs(sol + "(", left - 1, right)  # 使用一个左括号
            elif left < right:
                if left:
                    dfs(sol + "(", left - 1, right)  # 剩余左括号小于右括号，可以选择性来个括号
                dfs(sol + ")", left, right - 1)
        res = []
        dfs("", n, n)
        return res
```

【算法题目】【奇怪的DFS】Python 括号生成

![在这里插入图片描述](/static/img/images/04920.png)





# DFS+剪枝：直接超时：
```python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        def dfs(start, sol: List):
            # print(sol)
            if start > n:  # 结束条件，
                return
            if len(sol) >= 3:
                if sum(sol) == 0:
                    res.append(sol[:])
                return
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:  # 为了排除相同结果
                    continue
                sol.append(nums[i])
                dfs(i + 1, sol)
                sol.pop()
        nums.sort()
        n = len(nums)
        res = []
        dfs(0, [])
        return res
```

# 排序 + 双指针

双指针双向移动也能减少计算，拿到结果就能拜拜进行下一次，不像DFS没有太考虑数据的有序性，在DFS中的排序仅仅剪枝用了一下。

```python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()
        # 枚举 a
        for first in range(n):
            # 需要和上一次枚举的数不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # c 对应的指针初始指向数组的最右端
            third = n - 1
            target = -nums[first]
            # 枚举 b
            for second in range(first + 1, n):
                # 需要和上一次枚举的数不相同
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                # 需要保证 b 的指针在 c 的指针的左侧
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                # 如果指针重合，随着 b 后续的增加
                # 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if second == third:  # 指针位置性
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        return ans
```

【算法题目】【DFS】Python 三数之和 DFS+剪枝 排序 + 双指针

# 题目




```
5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
```

# 解答1 动态规划 转为最长子字符串（执行超时 200ms）

如果将字符串倒置，原问题变化到求最长子字符串问题：[https://blog.csdn.net/x1131230123/article/details/124176271](https://blog.csdn.net/x1131230123/article/details/124176271)。

下图是输入`"babad"`的dp，需要注意取的是第一次的i行j列。

![在这里插入图片描述](/static/img/images/04921.png)

```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 倒序字符串，求最长公共子串
        s1 = s[::-1]
        m, n = len(s), len(s1)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        maxlen = 0
        maxend = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s[i - 1] == s1[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = 0
                if maxlen < dp[i][j]: # 保留第一次最大的，字符串多个同长度回文只留第一次的
                    if n - j == i - dp[i][j]: # 判断回文位置，位置必须是同一个位置，比如输入acaabkaaca，回文不是acaa才行
                        maxlen = dp[i][j]
                        maxend = i
        return s[maxend - maxlen:maxend]
```

# 解答2 中心扩散 （1ms量级）

字符串非常长的时候，动态规划 $O(n^2)$ 的时间复杂度，计算量太大，而且停不下来，中心扩散法能够及时止住，时间复杂度虽然也是 $O(n^2)$ ，但期望下来小多了。

```python
class Solution:
    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1
    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        for i in range(len(s)):
            left1, right1 = self.expandAroundCenter(s, i, i)  # 奇数个，从本字符扩散
            left2, right2 = self.expandAroundCenter(s, i, i + 1)  # 偶数个，从本字符和下一个字符扩散
            if right1 - left1 > end - start:  # 保留最大的边界
                start, end = left1, right1
            if right2 - left2 > end - start:  # 保留最大的边界
                start, end = left2, right2
        return s[start: end + 1]
```

# 解答3 动态规划 直接

这个动态规划太难想了，建议别看了==
```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s
        max_len = 1
        begin = 0
        # dp[i][j] 表示 s[i:j] 是否是回文串
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 1
        # 递推开始
        # 先枚举子串长度
        for L in range(2, n + 1):
            # 枚举左边界，左边界的上限设置可以宽松一些
            for i in range(n):
                # 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                j = L + i - 1
                # 如果右边界越界，就可以退出当前循环
                if j >= n:
                    break
                if s[i] != s[j]:
                    dp[i][j] = 0
                else:
                    if j - i < 3:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                # 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    begin = i
        return s[begin:begin + max_len]
```

【算法题目】【动态规划】Python 最长回文子串

# 1 巧妙的思路





看到了一个巧妙的思路：

python3
```python
class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        h1 = 0
        h2 = 0
        for i in range(len(height)):
            h1 = max(h1,height[i])
            h2 = max(h2,height[-i-1])
            ans = ans + h1 + h2 -height[i]
        return  ans - len(height)*h1
```

![在这里插入图片描述](/static/img/images/04927.png)

![在这里插入图片描述](/static/img/images/04928.png)

# 2 如何理解

将循环中这句话`ans = ans + h1 + h2 -height[i]`分开理解，对于所有的遍历过程中的所有`h1` ，当`h1` 小于最大值，就会减去`height[i]` ，这样就得到了左边的雨水+ 右边整个面积。下图的红色表示了最终的数值。

![在这里插入图片描述](/static/img/images/04929.png)

对于所有的遍历过程中的所有`h2` ，当`h2` 小于等于最大值，就会减去`height[i]` ，这样就得到了右边的雨水+ 左边整个面积。下图的橘色表示了最终的数值。

![在这里插入图片描述](/static/img/images/04930.png)

将上面的2个面积加起来，会得到 所有的雨水+ `len(height)*h1` 。


我真是服了。

# 3 动态规划

动态规划没这个思路简单。不写了。

【算法题目】【动态规划】接雨水

员工参加考试，判断题X10（每个2分），单选题X10（每个4分），多选题X5（每个八分）。只能顺序作答，答对得分，答错不得分。答错三道，中止考试。输入考试结果分数，输出答题可能情况个数。





1 需要dfs传递的参数才写成参数，能全局变量就尽量全局。

2 这题传了开始位置、错误次数、分数，三者都是停止条件。

3 搜索也分回溯或者不回溯。

不回溯：

python：
```python
def cal(score_in):
    def dfs(start, error, score):
        if start == n:
            return
        if error >= 3:
            return
        if score == score_in:
            res.append(1)  # 此搜索路径是对的，已经拼凑出
            return
        if score > score_in:
            return
        dfs(start + 1, error, score + nums[start])  # 本题做对
        dfs(start + 1, error + 1, score)  # 本题做错
    nums = [2] * 10 + [4] * 10 + [8] * 5
    n = len(nums)
    res = []
    dfs(0, 0, 0)
    return len(res)
```

回溯：
```python
def cal(score_in):
    def dfs(start, error, score):
        if start == n:
            return
        if error >= 3:
            return
        if score == score_in:
            res.append(1)  # 此搜索路径是对的，已经拼凑出
            return
        if score > score_in:
            return
        for i in range(start, len(nums)):
            score += nums[i]  # 本题对
            dfs(i + 1, error, score)
            score -= nums[i]  # 回溯
            error += 1
    nums = [2] * 10 + [4] * 10 + [8] * 5
    n = len(nums)
    res = []
    dfs(0, 0, 0)
    return len(res)
```

【算法题目】【DFS】考试得分组合

# 1岛屿数量





![在这里插入图片描述](/static/img/images/04931.png)

题目很好理解，dfs来一套即可：

（1）二维的，没考虑特殊情况；

（2）对每个网格dfs，每次dfs往上下左右搜

（3）grid是list，在python里面会是一个全局，第一次搜到记一次搜到了一块岛屿，后面的dfs都是为了扫清上下左右的岛屿；

（4）dfs三要素：

a 如何结束

b 如何递归

c 如何剪枝，这里不需要

```python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(x,y,flagfrist):
            if x<0 or x>=m or y<0 or y>=n:
                return 
            if grid[x][y]=="1":
                if flagfrist==0:
                    res.append(1)
                    flagfrist=1
                grid[x][y]="0"
                dfs(x-1,y,flagfrist)
                dfs(x+1,y,flagfrist)
                dfs(x,y-1,flagfrist)
                dfs(x,y+1,flagfrist)
        m=len(grid)
        n=len(grid[0])
        res=[]
        for i in range(m):
            for j in range(n):
                dfs(i,j,0)
        return len(res)
```

# 2 岛屿中面积最大值

![在这里插入图片描述](/static/img/images/04932.png)

写dfs，把重点放在结束条件和如何递归上，多考虑搜索数结构，

能定义为全局变量的就定义为全局变量，**需要往下一级递归的变量才定义为dfs函数的参数**，不然会陷入乱糟糟的传参中！ 

```python
class Solution:
    def maxAreaOfIsland(self, grid: List[List[str]]) -> int:
        def dfs(x,y):
            if x<0 or x>=m or y<0 or y>=n:
                return 
            if grid[x][y]==1:
                area.append(1)
                grid[x][y]=0
                dfs(x-1,y)
                dfs(x+1,y)
                dfs(x,y-1)
                dfs(x,y+1)
        m=len(grid)
        n=len(grid[0])
        res=0
        for i in range(m):
            for j in range(n):
                area=[]
                dfs(i,j)
                res=max(len(area),res)
        return res
```

【算法题目】【DFS】岛屿数量 岛屿中面积最大值

# 1 组合





![在这里插入图片描述](/static/img/images/04933.png)

数字都不同，dfs搜索：
```python
from typing import List
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def dfs(start):
            if len(sol) == k:
                res.append(sol[:])
                return
            if start == len(nums):
                return
            for i in range(start, len(nums)):
                sol.append(nums[i])
                dfs(i + 1)
                sol.pop()
        res = []
        sol = []
        nums = list(range(1, n + 1))
        dfs(0)
        return res
```

# 2 组合总和

39. 组合总和

[https://leetcode-cn.com/problems/combination-sum/comments/](https://leetcode-cn.com/problems/combination-sum/comments/)

![在这里插入图片描述](/static/img/images/04934.png)

```python
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        temp = []
        def recursion(idx, res):
            if idx >= len(candidates) or res >= target:
                if res == target:
                    ans.append(temp[:])
                return
            temp.append(candidates[idx])
            recursion(idx, res + candidates[idx]) 
            temp.pop()
            recursion(idx + 1, res)
        recursion(0, 0)
        return ans 
```

```python
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(index,sol_sum,sol): # 序号，加和，选取的列表
            if sol_sum==target:
                res.append(sol[:])
                return
            if index==n or sol_sum>target:
                return
            dfs(index, sol_sum+candidates[index], sol+[candidates[index]]) # 选择上当前元素，继续搜
            dfs(index+1, sol_sum, sol) # 不选上当前元素，继续搜
        candidates.sort()
        n = len(candidates)
        res = []
        dfs(0,0,[])
        return res
```

```python
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(index,sol_sum,sol): # 序号，加和，选取的列表
            if sol_sum==target:
                res.append(sol[:])
                return
            if index==n or sol_sum>target:
                return
            # 解法1
            # dfs(index, sol_sum+candidates[index], sol+[candidates[index]]) # 选择上当前元素，继续搜
            # dfs(index+1, sol_sum, sol) # 不选上当前元素，继续搜
            # 解法2
            for i in range(index,n):
                sol_sum+=candidates[i]
                sol+=[candidates[i]]
                dfs(i, sol_sum, sol) # 基于此继续选择，传i，下一次就不会选到i左边的数
                sol_sum-=candidates[i]
                sol.pop()
        candidates.sort()
        n = len(candidates)
        res = []
        dfs(0,0,[])
        return res
```

# 3 组合总和2

![在这里插入图片描述](/static/img/images/04935.png)

[https://leetcode-cn.com/problems/combination-sum/comments/](https://leetcode-cn.com/problems/combination-sum/comments/)
```python
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(pos: int, rest: int):
            nonlocal sequence
            if rest == 0:
                ans.append(sequence[:])
                return
            if pos == len(freq) or rest < freq[pos][0]:
                return
            dfs(pos + 1, rest)
            most = min(rest // freq[pos][0], freq[pos][1])
            for i in range(1, most + 1):
                sequence.append(freq[pos][0])
                dfs(pos + 1, rest - i * freq[pos][0])
            sequence = sequence[:-most]
        freq = sorted(collections.Counter(candidates).items())
        ans = list()
        sequence = list()
        dfs(0, target)
        return ans
```

# 4 子集

![在这里插入图片描述](/static/img/images/04936.png)

[https://leetcode-cn.com/problems/subsets/](https://leetcode-cn.com/problems/subsets/)

![在这里插入图片描述](/static/img/images/04937.png)

[https://leetcode-cn.com/problems/subsets-ii/](https://leetcode-cn.com/problems/subsets-ii/)

【算法题目】【DFS】组合，组合总和1,2

面试官真是太资深，只有再深入学习才行了：





1 决策树、支持向量机、贝叶斯分类器 的数学知识；

2 mse损失函数反向传播推导，与权重联系；

3 项目事情；

4 coding：C++ 内存泄漏解决；

5 coding：python 一维maxpooling的时间复杂度优化；

【BIGO】 算法岗位面试

有n个台阶，青蛙一次只能跳1步到k步，请问有多少种跳法？





这个问题是一个经典的爬楼梯问题，可以使用递推方法解决。

设f[i]表示到达第i层台阶的跳法数，那么到达第i层台阶的跳法数可以由从第i-1，i-2...i-k层台阶跳上来得到，即：

f[i] = f[i-1] + f[i-2] + ... + f[i-k]

当然，这个递推式需要初始化，当i<k时，f[i] = 1，其中，i =1 为起点，f[i]=1.

因此，有n个台阶，青蛙一次只能跳1步到k步的跳法数为f[n]。

代码：

```python
def frog_steps(n, k):
    f = [1] + [0] * n
    for i in range(1, n+1):
        for j in range(1, min(i, k)+1):
            f[i] += f[i-j]
    return f[n]
print(frog_steps(n=4, k=3))
```

这里的n表示有n个台阶，k表示青蛙一次可以跳的最多步数。代码中的f数组用来存储到达第i层台阶的跳法数。 使用两个循环，外层循环是遍历到达第i层台阶的所有跳法，内层循环是遍历所有从第i-1，i-2...i-k层台阶跳上来的情况，最终将所有跳法数相加。返回第n个台阶的跳法数。

迭代法可以通过滚动数组来优化空间复杂度，下面是一种实现方式：

```python
def frog_steps_iteration(n, k):
    if n < k:
        return 1
    f = [1] + [0] * k
    for i in range(k+1, n+1):
        f[i % (k+1)] = sum(f[(i-j) % (k+1)] for j in range(1, k+1))
    return f[n % (k+1)]
print(frog_steps_iteration(n=4, k=3))
```

这里与递推类似，不同的是我们使用一个滚动数组f[i % (k+1)], 来存储到达第i层台阶的跳法数。空间复杂度是O(k),这里的n表示有n个台阶，k表示青蛙一次可以跳的最多步数。使用一个循环，遍历所有从第i-1，i-2...i-k层台阶跳上来的情况，最终将所有跳法数相加。返回第n个台阶的跳法数。

【算法题目】有n个台阶，青蛙一次只能跳1步到k步，请问有多少种跳法？

最长公共子序列  [https://leetcode-cn.com/problems/longest-common-subsequence/](https://leetcode-cn.com/problems/longest-common-subsequence/)





动态规划：
```python
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m,n=len(text1),len(text2)
        dp=[[0]*(n+1) for i in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                if text1[i-1]==text2[j-1]:
                    dp[i][j]=dp[i-1][j-1]+1
                else:
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])
        return dp[-1][-1]
```


最长重复子数组    [https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/](https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/)

动态规划：

![在这里插入图片描述](/static/img/images/04941.png)

```python
class Solution:
    def findLength(self, text1: List[int], text2: List[int]) -> int:
        m,n=len(text1),len(text2)
        dp=[[0]*(n+1) for i in range(m+1)]
        ans=0
        for i in range(1,m+1):
            for j in range(1,n+1):
                if text1[i-1]==text2[j-1]:
                    dp[i][j]=dp[i-1][j-1]+1
                else:
                    dp[i][j]=0
                ans=max(dp[i][j],ans)
        return ans
```

【算法题目】【动态规划】最长公共子序列 最长重复子数组 最长公共子字符串

ref:[https://blog.csdn.net/u010089444/article/details/70854510](https://blog.csdn.net/u010089444/article/details/70854510)





![在这里插入图片描述](/static/img/images/04977.png)

![在这里插入图片描述](/static/img/images/04978.png)

所以（python）：

```python
class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        def find(x,y):
            if not (x<len(matrix) and y ):
                return False
            elif matrix[x][y-1]==target:
                return True
            elif matrix[x][y-1]>target:
                return find(x,y-1) # 目标值小，往左子树找
            else:
                return find(x+1,y) # 目标值大，往右子树找
        if len(matrix):
            return find(0,len(matrix[0]))
        else:
            return False
```

【算法题目】行列递增矩阵中查找一个数值 Python

给定一个二维的 0-1 矩阵，其中 0 表示海洋，1 表示陆地。单独的或相邻的陆地可以形成岛屿，每个格子只与其上下左右四个格子相邻。求最大的岛屿面积。





Input:

[[1,0,1,1,0,1,0,1],

[1,0,1,1,0,1,1,1],

[0,0,0,0,0,0,0,1]]

Output: 6


思路：

有时我们可能会需要对已经搜索过的节点进行标记，以防止在遍历时重复搜索某个节点，这种做法叫做状态记录或记忆化（memoization）。

一般来说，深度优先搜索类型的题可以分为主函数和辅函数，主函数用于遍历所有的搜索位置，判断是否可以开始搜索，如果可以即在辅函数进行搜索。辅函数则负责深度优先搜索的递归调用。当然，我们也可以使用栈（stack）实现深度优先搜索，但因为栈与递归的调用原理相同，而递归相对便于实现，因此刷题时笔者推荐使用递归式写法，同时也方便进行回溯（见下节）。不过在实际工程上，直接使用栈可能才是最好的选择，一是因为便于理解，二是更不易出现递归栈满的情况。我们先展示使用栈的写法：

（1）遍历所有元素

（2）遇到1的直接入栈计算，栈里面所有元素在四个方向有1的继续入栈

（3）标记好已经搜索过的地方

```python
def maxAreaOfIsland(grid):
    direction = [-1, 0, 1, 0, -1]
    m = len(grid)  # 行
    n = len(grid[0]) if m else 0  # 列
    area = 0
    for i in range(0, m):
        for j in range(0, n): # （1）遍历所有元素
            if grid[i][j]:  # 首先得确认这是一块陆地，才能往下发展
                local_area = 1
                grid[i][j] = 0
                island = []
                island.append([i, j])
                while len(island): # 遇到1的直接入栈计算，栈里面所有元素在四个方向有1的继续入栈
                    r, c = island.pop()  # 栈顶元素
                    for k in range(0, 4):  # 栈顶元素的四个方向
                        x = r + direction[k]
                        y = c + direction[k + 1]
                        if x >= 0 and x < m and y >= 0 and y < n and grid[x][y] == 1:  # 栈顶元素的这个方向遇到的是不是1
                            grid[x][y] = 0
                            local_area += 1
                            island.append([x, y])
                area = max(area, local_area)
    return area
grid_t = [[1, 0, 1, 1, 0, 1, 0, 1],
          [1, 0, 1, 1, 0, 1, 1, 1],
          [0, 0, 0, 0, 0, 0, 0, 1]]
print(maxAreaOfIsland(grid_t))
```

在辅函数里，一个一定要注意的点是辅函数内递归搜索时，边界条件的判定。边界判定一般

有两种写法，一种是先判定是否越界，只有在合法的情况下才进行下一步搜索（即判断放在调用

递归函数前）；另一种是不管三七二十一先进行下一步搜索，待下一步搜索开始时再判断是否合

法（即判断放在辅函数第一行）。

此外的主函数+辅助函数的写法（C++）:

```c
vector<int> direction { -1, 0, 1, 0, -1 };
/* 主函数 */
int maxAreaOfIsland( vector<vector<int> > & grid )
{
 if ( grid.empty() || grid[0].empty() )
  return(0);
 int max_area = 0;
 for ( int i = 0; i < grid.size(); ++i )
 {
  for ( int j = 0; j < grid[0].size(); ++j )
  {
   if ( grid[i][j] == 1 )
   {
    max_area = max( max_area, dfs( grid, i, j ) );
   }
  }
 }
 return(max_area);
}
/* 辅函数 */
int dfs( vector<vector<int> > & grid, int r, int c )
{
 if ( grid[r][c] == 0 )
  return(0);
 grid[r][c] = 0;
 int x, y, area = 1;
 for ( int i = 0; i < 4; ++i )
 {
  x = r + direction[i], y = c + direction[i + 1];
  if ( x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() )
  {
   area += dfs( grid, x, y );
  }
 }
 return(area);
}
```


```c
/* 主函数 */
int maxAreaOfIsland( vector<vector<int> > & grid )
{
 if ( grid.empty() || grid[0].empty() )
  return(0);
 int max_area = 0;
 for ( int i = 0; i < grid.size(); ++i )
 {
  for ( int j = 0; j < grid[0].size(); ++j )
  {
   max_area = max( max_area, dfs( grid, i, j ) );
  }
 }
 return(max_area);
}
/* 辅函数 */
int dfs( vector<vector<int> > & grid, int r, int c )
{
 if ( r < 0 || r >= grid.size() ||
      c < 0 || c >= grid[0].size() || grid[r][c] == 0 )
 {
  return(0);
 }
 grid[r][c] = 0;
 return(1 + dfs( grid, r + 1, c ) + dfs( grid, r - 1, c ) +
        dfs( grid, r, c + 1 ) + dfs( grid, r, c - 1 ) );
}
```

参考：LeetCode 101：和你一起你轻松刷题（C++）

【算法题目】【DFS】岛屿的最大面积

https://zhuanlan.zhihu.com/p/68358814





![在这里插入图片描述](/static/img/images/00464.png)

抛硬币多少次才连续两次正面朝上

[https://zhuanlan.zhihu.com/p/96229700](https://zhuanlan.zhihu.com/p/96229700)

匈牙利算法 二分图匹配 求二分图的最大匹配数和最小点覆盖数

![在这里插入图片描述](/static/img/images/00956.png)





[https://leetcode-cn.com/problems/house-robber/solution/dong-tai-gui-hua-jie-ti-si-bu-zou-xiang-jie-cjavap/](https://leetcode-cn.com/problems/house-robber/solution/dong-tai-gui-hua-jie-ti-si-bu-zou-xiang-jie-cjavap/)

作者：nettee

链接：https://leetcode-cn.com/problems/house-robber/solution/dong-tai-gui-hua-jie-ti-si-bu-zou-xiang-jie-cjavap/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

动态规划的的四个解题步骤是：

1 定义子问题

![在这里插入图片描述](/static/img/images/00957.png)

2 写出子问题的递推关系

![在这里插入图片描述](/static/img/images/00958.png)

![在这里插入图片描述](/static/img/images/00959.png)


3 确定 DP 数组的计算顺序

![在这里插入图片描述](/static/img/images/00960.png)

![在这里插入图片描述](/static/img/images/00961.png)

```python
def rob(self, nums: List[int]) -> int:
    if len(nums) == 0:
        return 0
    # 子问题：
    # f(k) = 偷 [0..k) 房间中的最大金额
    # f(0) = 0
    # f(1) = nums[0]
    # f(k) = max{ rob(k-1), nums[k-1] + rob(k-2) }
    N = len(nums)
    dp = [0] * (N+1)
    dp[0] = 0
    dp[1] = nums[0]
    for k in range(2, N+1):
        dp[k] = max(dp[k-1], nums[k-1] + dp[k-2])
    return dp[N]
作者：nettee
链接：https://leetcode-cn.com/problems/house-robber/solution/dong-tai-gui-hua-jie-ti-si-bu-zou-xiang-jie-cjavap/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
```

4 空间优化（可选）

![在这里插入图片描述](/static/img/images/00962.png)

![在这里插入图片描述](/static/img/images/00963.gif)



```python
def rob(self, nums: List[int]) -> int:
    prev = 0
    curr = 0
    # 每次循环，计算“偷到当前房子为止的最大金额”
    for i in nums:
        # 循环开始时，curr 表示 dp[k-1]，prev 表示 dp[k-2]
        # dp[k] = max{ dp[k-1], dp[k-2] + i }
        prev, curr = curr, max(curr, prev + i)
        # 循环结束时，curr 表示 dp[k]，prev 表示 dp[k-1]
    return curr
作者：nettee
链接：https://leetcode-cn.com/problems/house-robber/solution/dong-tai-gui-hua-jie-ti-si-bu-zou-xiang-jie-cjavap/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
```

198. 打家劫舍 【动态规划】 好文分享

先序遍历和后序遍历为什么不能唯一地确定一棵树？：





[https://blog.csdn.net/GYQJN/article/details/52709912](https://blog.csdn.net/GYQJN/article/details/52709912)

只有每个节点度为2或者0的时候前序和后序才能唯一确定一颗二叉树，只有一个子节点是无法确定的，因为你无法判断他是左子树还是右子树。

105. 从前序与中序遍历序列构造二叉树

[https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)

106. 从中序与后序遍历序列构造二叉树

[https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)

108. 根据前序和后序遍历构造二叉树

[https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/)



从来都是用来当填空题的。现在要求写程序。

比如：
```c
     A
  B     C
F      D  E
```

a=['A','B','F','C','D','E']   #前序样子

b=['F','B','A','D','C','E']   #中序样子

c=['F','B','D','E','C','A']  #后序样子

规律：

![在这里插入图片描述](/static/img/images/00964.png)

要点：树的前序遍历第一个是根节点。长度关系。子数递归满足此条件。


```python
from typing import List
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def buildTreeFromPreorderInorder(self, preorder: List[str], inorder: List[str]) -> TreeNode:
        n = len(preorder)
        # 构造哈希映射，帮助我们快速定位根节点
        index = {element: i for i, element in enumerate(inorder)}
        def helper(preorder_left: int, preorder_right: int, inorder_left: int, inorder_right: int):
            if preorder_left > preorder_right:
                return None
            # 前序遍历中的第一个节点就是根节点
            preorder_root = preorder_left
            # 在中序遍历中定位根节点
            inorder_root = index[preorder[preorder_root]]
            # 先把根节点建立出来
            root = TreeNode(preorder[preorder_root])
            # 得到左子树中的节点数目
            size_left_subtree = inorder_root - inorder_left
            # 递归地构造左子树，并连接到根节点
            # 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
            root.left = helper(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1)
            # 递归地构造右子树，并连接到根节点
            # 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
            root.right = helper(preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right)
            return root
        return helper(0, n - 1, 0, n - 1)
    def buildTreeFromInorderPostorder(self, inorder , postorder):
        temp=postorder[:]
        def helper(in_left, in_right):
            # 如果这里没有节点构造二叉树了，就结束
            if in_left > in_right:
                return None
            # 选择 post_idx 位置的元素作为当前子树根节点
            val = temp.pop()
            root = TreeNode(val)
            # 根据 root 所在位置分成左右两棵子树
            index = idx_map[val]
            # 构造右子树
            root.right = helper(index + 1, in_right)
            # 构造左子树
            root.left = helper(in_left, index - 1)
            return root
        # 建立（元素，下标）键值对的哈希表
        idx_map = {val: idx for idx, val in enumerate(inorder)}
        return helper(0, len(inorder) - 1)
    def constructFromPreorderPostorder(self, pre, post):
        if not pre:
            return None
        node = TreeNode(pre[0])
        if len(pre) == 1:
            return node
        i = post.index(pre[1])
        node.left = self.constructFromPreorderPostorder(pre[1:i + 2], post[:i + 1])
        node.right = self.constructFromPreorderPostorder(pre[i + 2:], post[i + 1:-1])
        return node
    def preorderTraversal(self, root: TreeNode) -> List[str]:
        def preorder(root: TreeNode):
            if not root:
                return
            res.append(root.val)
            preorder(root.left)
            preorder(root.right)
        res = list()
        preorder(root)
        return res
    def inorderTraversal(self, root: TreeNode) -> List[str]:
        def preorder(root: TreeNode):
            if not root:
                return
            preorder(root.left)
            res.append(root.val)
            preorder(root.right)
        res = list()
        preorder(root)
        return res
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        def postorder(root: TreeNode):
            if not root:
                return
            postorder(root.left)
            postorder(root.right)
            res.append(root.val)
        res = list()
        postorder(root)
        return res
a = ['A', 'B', 'F', 'C', 'D', 'E']  #前序样子
b = ['F', 'B', 'A', 'D', 'C', 'E']  #中序样子
c = ['F', 'B', 'D', 'E', 'C', 'A']  #后序样子
onexianxu=Solution().buildTreeFromInorderPostorder(b,c)
print('先序',Solution().preorderTraversal(onexianxu))
onezhong=Solution().constructFromPreorderPostorder(a, c)
print('中序',Solution().inorderTraversal(onezhong))
onehouxu=Solution().buildTreeFromPreorderInorder(a,b)
print('后序',Solution().postorderTraversal(onehouxu))
```

python 105. 从前序与中序遍历序列构造二叉树 106. 从中序与后序遍历序列构造二叉树 108. 根据前序和后序遍历构造二叉树

开始自己写了一个全排列，不优雅。





python有全排列的系统库：

> from itertools import permutations

题目描述

> 计算24点是一种扑克牌益智游戏，随机抽出4张扑克牌，通过加(+)，减(-)，乘(*),

> 除(/)四种运算法则计算得到整数24，本问题中，扑克牌通过如下字符或者字符串表示，其中，小写joker表示小王，大写JOKER表示大王： 

> 

>                    3 4 5 6 7 8 9 10 J Q K A 2 joker JOKER

> 

> 本程序要求实现：输入4张牌，输出一个算式，算式的结果为24点。 

> 

> 详细说明： 

> 

> 1.运算只考虑加减乘除运算，没有阶乘等特殊运算符号，友情提醒，整数除法要当心； 

> 2.牌面2~10对应的权值为2~10, J、Q、K、A权值分别为为11、12、13、1； 

> 3.输入4张牌为字符串形式，以一个空格隔开，首尾无空格；如果输入的4张牌中包含大小王，则输出字符串“ERROR”，表示无法运算； 

> 4.输出的算式格式为4张牌通过+-*/四个运算符相连，中间无空格，4张牌出现顺序任意，只要结果正确； 

> 5.输出算式的运算顺序从左至右，不包含括号，如1+2+3*4的结果为24

> 6.如果存在多种算式都能计算得出24，只需输出一种即可，如果无法得出24，则输出“NONE”表示无解。


python

```python
# 思路：对所有数字全排列，计算每种排列能否凑成24（题目默认按照先后顺序计算，即（(a+b)+c))+d模式。
# 如果joker 或 JOKER 在输入序列中，返回ERROR
# 当有一个满足的解时，返回；遍历完所有排列，如果没有满足的解，返回NONE
from itertools import permutations
while True:
    try:
        def check(exp):  # 为了排除中间/0的情况，并且若等式值为24，返回True
            try:
                return int(eval(exp) == 24)
            except:
                return False
        def game24(pokers):
            dic = {'A': '1', '2': '2', '3': '3', '4': '4', '5': '5', '6': '6', '7': '7', '8': '8', '9': '9', '10': '10',
                   'J': '11', 'Q': '12', 'K': '13'}
            ops = r'+-*/'
            exp = '((%s %s %s) %s %s )%s %s'  ## 这道题默认括号是这么加的
            for a in permutations(pokers):  ## nums 的全排列
                for op1 in ops:
                    for op2 in ops:
                        for op3 in ops:
                            if check(exp % (dic[a[0]], op1, dic[a[1]], op2, dic[a[2]], op3, dic[a[3]])):
                                result = a[0] + op1 + a[1] + op2 + a[2] + op3 + a[3]  ## 这题只需要求出一个满足要求的等式即可
                                return result
            return 'NONE'
        pokers = input().split(' ')
        if 'joker' in pokers or 'JOKER' in pokers:
            print('ERROR')
        else:
            print(game24(pokers))
    except:
        break
```

24点游戏的暴力美学

[https://blog.csdn.net/darkrabbit/article/details/89409548](https://blog.csdn.net/darkrabbit/article/details/89409548)






（1） 出栈序列共有多少种可能？

（2） 求出所有出栈（入栈）序列。

（3） 给出一个出栈序列，问栈的容量最少需要多少？

（4） 给出一个（或多个）出栈序列，问此序列是不是（哪一个序列不是）原序列混洗得到的？


![在这里插入图片描述](/static/img/images/00970.png)

python

题目描述

给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号，火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出站了，先进站的才能出站。

要求输出所有火车出站的方案，以字典序排序输出。
```python
while True:
    try:
        n = int(input())
        trains = [  str(1+i)  for i in range(n)]
        res = []
        def rec_trains(cur_idx, in_trains, out_trains):
            # 如果原始火车列表的最后一个元素已经进站，此时只能出站，将入站列表中的火车倒序加入出站火车中
            if trains[-1] in in_trains:
                res.append(' '.join(out_trains + in_trains[::-1]))
                return
            # 如果进站列表为空，此时只能进站，进站列表加上当前火车，出站列表不变
            elif in_trains == []:
                rec_trains(cur_idx + 1, in_trains + [trains[cur_idx]], out_trains)
            # 否则，就既有可能进站也有可能出站
            else:
                # 出站，当前火车索引不变，进站火车列表减去最后一个元素，出站列表加上进站列表刚刚出站的火车
                rec_trains(cur_idx, in_trains[:-1], out_trains + [in_trains[-1]])
                # 进站，当前火车索引加1，进站列表加上当前火车，出站列表不变
                rec_trains(cur_idx + 1, in_trains + [trains[cur_idx]], out_trains)
        rec_trains(0, [], [])
        res.sort()
        print(len(res))
    except:
        break
```

数据结构 栈混洗 个数 Stack Shuffling 卡特兰数

介绍：





[https://www.cnblogs.com/frankchenfu/p/7107019.html](https://www.cnblogs.com/frankchenfu/p/7107019.html)

应用

![在这里插入图片描述](/static/img/images/00971.png)

```python
import bisect
def max_order(lists):
    list_num = []
    list_max = []
    for i in lists:
        # bisect_left把i插入list_num，使得list_num还是升序，返回index。insort才是就地插入
        local = bisect.bisect_left(list_num, i)
        if local == len(list_num):  # 最后一个
            list_num.append(i)  # 最大值放最后
            list_max.append(local + 1)  # 记录每个元素插在哪个位置了
        else:
            list_num[local] = i  # 不是最大就替换，给后面更多机会
            list_max.append(local + 1)  # 记录每个元素插在哪个位置了
    return list_max
while True:
    try:
        people_num = int(input())
        height_list = list(map(int, input().split()))
        result_1 = max_order(height_list)  # 升序最长
        result_2 = max_order(height_list[::-1])[::-1]  # 降序最长
        print(people_num - max(map(sum, zip(result_1, result_2))) + 1)
    except BaseException as er:
        # print("fault line is", er.__traceback__.tb_lineno)
        break
```

输入

8

186 186 150 200 160 130 197 200

最后

result_1 

[1, 1, 1, 2, 2, 1, 3, 4]

result_2 

[3, 3, 2, 3, 2, 1, 1, 1]

所以要出队这么多人：

4

【算法题目】最长上升子序列 合唱队形 【动态规划】

推荐阅读：





百度百科：[https://baike.baidu.com/item/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/2416931?fr=aladdin#reference-\[9\]-841810-wrap](https://baike.baidu.com/item/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/2416931?fr=aladdin#reference-%5B9%5D-841810-wrap)

java实现：[https://blog.csdn.net/Cobbyer/article/details/108127742](https://blog.csdn.net/Cobbyer/article/details/108127742)

计算机常用算法与程序设计案例教程： [https://max.book118.com/html/2019/0122/6053000055002003.shtm](https://max.book118.com/html/2019/0122/6053000055002003.shtm)

知乎：[https://zhuanlan.zhihu.com/p/93857890](https://zhuanlan.zhihu.com/p/93857890)

## 1 0-1背包

![在这里插入图片描述](/static/img/images/00972.png)

对于输入

4件物品  背包能承受的最大重量为10

单体重量2  单体价值1

单体重量3  单体价值3

...
```python
4 10
1 1
3 3
4 5
7 9
```

动态规划：
```python
numandweight = list(map(int, input().split(' ')))  # 读取输入
N = numandweight[0]  # N件物品
V = numandweight[1]  # 背包能承受的最大重量为V
w = [0]  # 第一个元素无用  单体重量
c = [0]  # 第一个元素无用  单体价值
for i in range(N):
    temp = list(map(int, input().split(' ')))  # 读取输入
    w.append(temp[0])
    c.append(temp[1])
# 创建二维list
dp = []
for i in range(N + 1):
    dp.append([])
    for j in range(V + 1):
        dp[i].append(0)
for i in range(1, N + 1):  # 表示当前有第i个物品可以拿
    for j in range(1, V + 1):  # 表示当前背包的容量为j
        if j < w[i]:  # 如果当前背包容量j放不下重量为w[i]的物体
            dp[i][j] = dp[i - 1][j]  # 不拿 i 物品，此时背包价值依旧等于成功拿了上一个物体时的价值
        else:
            # 背包装得下，但是考虑一下值不值得拿，比较一下拿了和没拿前后背包价值的变化，取最大的方法
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i])
# 打印二维list
for i in range(len(dp)):
    print(dp[i])
```

输出dp：

```python
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 1, 3, 4, 4, 4, 4, 4, 4, 4]
[0, 1, 1, 3, 5, 6, 6, 8, 9, 9, 9]
[0, 1, 1, 3, 5, 6, 6, 9, 10, 10, 12]
```

dp表中每一个dp[i]的值只与dp[i-1]有关系，即后无效性原则。

 `dp[i][j]`表示前`i`件物品恰放入一个容量为`j`的背包可以获得的最大价值。

 `dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i])` 表示 考虑一下值不值得拿，比较一下拿了和没拿前后背包价值的变化，取最大的方法。

 整个dp只有最终的`dp[N][V]` 有意义，其他数据都是为了求出`dp[N][V]` 而做的变化。

改进代码：

```python
numandweight = list(map(int, input().split(' ')))  # 读取输入
N = numandweight[0]  # N件物品
V = numandweight[1]  # 背包能承受的最大重量为V
w = [0]  # 第一个元素无用  单体重量
c = [0]  # 第一个元素无用  单体价值
for i in range(N):
    temp = list(map(int, input().split(' ')))  # 读取输入
    w.append(temp[0])
    c.append(temp[1])
dp = [0 for i in range(V + 1) ]
for i in range(1, N + 1):  # 表示当前有第i个物品可以拿
    for j in range(V, 0, -1):  # 从后往前推
        if j >= w[i]:  # 如果当前背包容量j 可以放下 重量为w[i]的物体
            dp[j] = max(dp[j], dp[j - w[i]] + c[i])
    print(dp)
```

## 2 完全背包

问题描述：给定 N 种物品每种物品**都有无限件可用**，物品的重量为 w[i]，物品的价值为 c[i]。现挑选物品放入背包中，假定背包能承受的最大重量为 V，问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

```python
numandweight = list(map(int, input().split(' ')))  # 读取输入
N = numandweight[0]  # N件物品
V = numandweight[1]  # 背包能承受的最大重量为V
w = [0]  # 第一个元素无用  单体重量
c = [0]  # 第一个元素无用  单体价值
for i in range(N):
    temp = list(map(int, input().split(' ')))  # 读取输入
    w.append(temp[0])
    c.append(temp[1])
# 创建二维list
dp = []
for i in range(N + 1):
    dp.append([])
    for j in range(V + 1):
        dp[i].append(0)
for i in range(1, N + 1):  # 表示当前有第i个物品可以拿
    for v in range(1, V + 1):  # 表示当前背包的容量为j
        dp[i][v]=0
        # 最多可以放nCount个物品i
        nCount = v // w[i]
        # 和01背包的区别就在这里，01
        # 背包只有两种状态：放与不放
        # 而完全背包可以放0到k个物品i，同样是取最大值
        for k in range(nCount+1):
            dp[i][v] = max(dp[i][v], dp[i - 1][v - k * w[i]] + k * c[i]) 
# 打印二维list
for i in range(len(dp)):
    print(dp[i])
```

输入：

```python
4 5
1 2
2 4
3 4
4 5
```

输出

```python
[0, 0, 0, 0, 0, 0]
[0, 2, 4, 6, 8, 10]
[0, 2, 4, 6, 8, 10]
[0, 2, 4, 6, 8, 10]
[0, 2, 4, 6, 8, 10]
```

## 3 多重背包

问题描述：给定 N 种物品每种物品 i 都有 s[i] 件可用，物品的重量为 w[i]，物品的价值为 c[i]。现挑选物品放入背包中，假定背包能承受的最大重量为 V，问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

```python
numandweight = list(map(int, input().split(' ')))  # 读取输入
N = numandweight[0]  # N件物品
V = numandweight[1]  # 背包能承受的最大重量为V
w = [0]  # 第一个元素无用  单体重量
c = [0]  # 第一个元素无用  单体价值
s = [0]  # 第一个元素无用  有多少件
for i in range(N):
    temp = list(map(int, input().split(' ')))  # 读取输入
    w.append(temp[0])
    c.append(temp[1])
    s.append(temp[2])
# 创建二维list
dp = []
for i in range(N + 1):
    dp.append([])
    for j in range(V + 1):
        dp[i].append(0)
for i in range(1, N + 1):  # 表示当前有第i个物品可以拿
    for j in range(V,-1,-1 ):  # 表示当前背包的容量为j
        for k in range(0, s[i] + 1):
            if j>=k * w[i]:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * c[i])
# 打印二维list
for i in range(len(dp)):
    print(dp[i])
```

输入

```python
4 5
1 2 3
2 4 1
3 4 3
4 5 2
```

输出

```python
[0, 0, 0, 0, 0, 0]
[0, 2, 4, 6, 6, 6]
[0, 2, 4, 6, 8, 10]
[0, 2, 4, 6, 8, 10]
[0, 2, 4, 6, 8, 10]
```