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