参考：[https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/wo-xie-le--9c7a4/](https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/wo-xie-le--9c7a4/)






#  1 基本介绍

二分查找法（Binary Search）是一种在**有序数组**中查找某一特定元素的搜索算法。其基本思想是，首先将整个有序数列分成前后两部分，判断在哪个部分中可能会找到要查找的数，然后递归地在那个部分中查找。

具体来说，首先选择数列的中间元素。如果要查找的数比中间元素小，则在数列的左半部分继续查找；如果要查找的数比中间元素大，则在数列的右半部分继续查找；如果相等，则找到了要查找的数。这样一直递归进行，直到找到要查找的数或者整个数列被查找完。

二分查找法的时间复杂度为 O(log n)，其中 n 是数列中的元素个数。由于其在有序数列中查找元素的时间复杂度较低，因此常用于大规模有序数列的查找。

> 二分查找并不简单，Knuth 大佬（发明 KMP 算法的那位）都说二分查找：思路很简单，细节是魔鬼。

- 有哪些细节：

> while循环中使用 low <= high 还是 low < high ？ 

> if条件里写<还是<=? 是low = mid +1？

> 还是low = mid ？



# 2 基本的二分查找

基本的二分查找中有序数组里的元素没有重复数值，而二分查找的目的就是找到符合条件的下标。

比如想在有序数组 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] 中找到元素5的index，该如何写python代码呢：

```python
def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:  # 结束条件是 low > high， 为什么不用<符号呢：因为当low=high时，还需要判断一次，不然[low,high]就会被漏掉
        mid = (low + high) // 2  # 和mid=low+(high-low)//2是一样的结果，low+(high-low)//2可以防止大数溢出
        if arr[mid] < x:
            low = mid + 1  # 在区间 [mid+1, high] 中查找
        elif arr[mid] > x:
            high = mid - 1  # 在区间 [low, mid-1] 中查找
        elif arr[mid] == x:
            return mid
    return -1
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
x = 5
result = binary_search(arr, x)
if result != -1:
    print(f"Element is present at index {result}")
else:
    print("Element is not present in array")
```

# 3 左边界 vs 右边界，查找相等的元素

当有序数组中存在重复值，即是由多个元素可以满足条件，返回哪一个下标更合适呢？

比如 arr = [1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9]， 找数值5，那么左边界index是4，右边界index是6。 

如果有序数组中有重复值，并且你想找到左边界的下标，你可以在二分查找的基础上，做一些改变来实现这个功能。

下面的代码展示了左边界和右边界的代码：

```python
def binary_search_leftright(arr, x):
    low = 0
    high = len(arr) - 1
    result = -1
    while low <= high:  # 结束条件是 low > high， 为什么不用<符号呢：因为当low=high时，还需要判断一次，不然[low,high]就会被漏掉
        mid = (low + high) // 2  # 和mid=low+(high-low)//2是一样的结果，low+(high-low)//2可以防止大数溢出
        if arr[mid] < x:
            low = mid + 1  # 在区间 [mid+1, high] 中查找
        elif arr[mid] > x:
            high = mid - 1  # 在区间 [low, mid-1] 中查找
        elif arr[mid] == x:
            result = mid  # 记录符合条件的下标
            # high = mid - 1  # 在区间 [low, mid-1] 中查找，这就很灵性，意味着找到了，但是还要继续找，而且趋势是往左找. 即找左边界。
            low = mid + 1  # 在区间 [mid+1, high] 中查找，这就很灵性，意味着找到了，但是还要继续找，而且趋势是往右找. 即找右边界。
    return result
arr = [1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9]
x = 5
result = binary_search_left(arr, x)
if result != -1:
    print(f"Element is present at index {result}")
else:
    print("Element is not present in array")
```

# 4 难度升级，找到 x<6 的右边界

在 arr = [4, 4, 5, 5, 6, 6, 7, 8, 9] 中找到一个元素x，满足x<6，且x是右边界元素：
```python
def binary_search_right(arr, x):
    low = 0
    high = len(arr) - 1
    while low < high:
        mid = (low + high) // 2
        if arr[mid] < x:
            low = mid + 1  # 继续在[mid+1, high]中查找，因为想找右边界
        else:
            high = mid  # 为什么不是mid-1呢?
    if arr[high] >= x:
        return high - 1
    else:
        return high
arr = [4, 4, 5, 5, 6, 6, 7, 8, 9]
x = 6
result = binary_search_right(arr, x)
print(result)
```

函数返回 high - 1 或者返回high。


- 如果将条件改为while low <= high呢，这样不可以吗？

> 如果你将循环的条件改为 while low <= high，在数组中查找小于目标值的右边界的时候是会有问题的。

> 

> 当low==high时，如果arr[high] >= x 那么最终返回值就是high -1,而实际上并不是小于目标值的右边界。

> 

> 因此，在二分查找中查找右边界时，循环条件应该是 low < high.

> 

> 这样当循环结束时，high指向的就是第一个大于等于目标值的位置，而high - 1就是小于目标值的右边界

> 

> 所以，在二分查找中查找右边界时，循环条件应该是 low < high 而非 low <= high,这是为了确保查找的正确性

> 

> 除此之外，还可能发生死循环。


- 那为什么是high = mid ，而不是high = mid -1？

> 在查找小于目标值的右边界时，如果循环条件是 low < high, 当 arr[mid] >= x 时,如果 high = mid -1 会使得 high 不满足循环条件,从而导致循环终止，而不是移动到小于目标值的右边界。

> 

> 而赋值high = mid会使得high = mid或者 high =

> mid-1,这样high总是满足循环条件且正确地找到了第一个大于等于目标值的位置,而high-1就是小于目标值的右边界。

> 

> 所以如果你想在查找小于目标值的右边界时，应该让 high = mid。这样可以保证查找的正确性。


# 5 找到 x>5 的左边界

在 arr = [4, 4, 5, 5, 6, 6, 7, 8, 9] 中找到一个元素x，满足x>5，且x是左边界元素：

```python
def binary_search_left(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] <= x:
            low = mid + 1
        else:
            high = mid - 1
    return low
arr = [4, 4, 5, 5, 6, 6, 7, 8, 9]
x = 5
result = binary_search_left(arr, x)
print(result)
```

或者：

```python
def binary_search_left(arr, x):
    low = 0
    high = len(arr)
    while low < high:
        mid = (low + high) // 2
        if arr[mid] <= x:
            low = mid + 1
        else:
            high = mid 
    return low
```


# 6 总结模板

当使用 "while low <= high" 时，要想结束循环，就需要更严格的判断，从而就不需要再单独对low 和high 进行特判。

如果要查找左边界（x>5的左边界）：

```python
def binary_search_left(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] <= x: # 如果是x>=5，这里就需要改变查找区间
            low = mid + 1
        else:
            high = mid - 1
    return low
```

如果要查找右边界（x<6的右边界）：

```python
def binary_search_right(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < x: # 如果是x<=6，这里就需要改变查找区间
            low = mid + 1
        else:
            high = mid - 1
    return high
```

【算法题目】一文搞懂二分查找法

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





普通二叉树，每个节点的数值不相同。写一个函数，输入是树的根节点和要删除的节点的集合，删除某个节点意味着去除掉和这个节点的关联，剩下的都是子树，函数返回剩余子树数量。

input：root，｛1｝

output：2

input：root，｛1,,2,5｝

output：2

input：root，｛1,,2｝

output：3

input：root，｛4｝

output：3

input：root，｛4,9｝

output：2


程序还有点问题：
```python
import copy
from typing import Set
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def getSubTree(root: Node, elements: Set, node_del=False) -> int:
"""
    if not elements or root is None:
        return 0
    if root.val in elements:
        elements = copy.deepcopy(elements)
        elements.remove(root.val)
        left_num = 1 + getSubTree(root.left, elements, True) if root.left is not None else 0
        right_num = 1 + getSubTree(root.right, elements, True) if root.right is not None else 0
        if node_del:
            return left_num + right_num - 1
        return left_num + right_num
    else:
        left_num = getSubTree(root.left, elements, False) if root.left is not None else 0
        right_num = getSubTree(root.right, elements, False) if root.right is not None else 0
        return left_num + right_num
        """
root = Node(1)
root.left = tree2 = Node(2)
root.right = tree3 = Node(3)
tree2.left = tree4 = Node(4)
tree2.right = tree5 = Node(5)
tree3.left = tree6 = Node(6)
tree3.right = tree7 = Node(7)
tree4.left = tree8 = Node(8)
tree4.right = tree9 = Node(9)
print(getSubTree(root, {1, 2, 5}))
```

【算法题目】【DFS】【一点资讯面试题】二叉树删除节点剩余子树数量

浮点数的 n次方根：





牛顿迭代法：
```python
class Solution:
    def sqrt_n(self, y, n) -> int:
        # f(x)=x**n-y=0
        # f`(x)=n*x^(n-1)
        # x=x-(x**n-y)/(n*2^(n-1))
        if n == 0:
            return 1
        # x1 的 n1 次方
        def pow1(x1, n1):
            if n1 == 0:
                return 1
            y1 = pow1(x1, n1 // 2)
            return y1 * y1 if n1 % 2 == 0 else y1 * y1 * x1
        x = 1  # 牛顿不动点迭代法
        while True:
            x2 = x - (pow1(x, n) - y) / (n * pow1(x, n - 1))
            if abs(x2 - x) < 1e-6:
                break
            x = x2
        return x2
```

二分查找：
```python
class Solution:
    def sqrt_n(self, y, n) -> int:
        assert n > 0
        # x1 的 n1 次方
        def pow1(x1, n1):
            if n1 == 0:
                return 1
            y1 = pow1(x1, n1 // 2)
            return y1 * y1 if n1 % 2 == 0 else y1 * y1 * x1
        # 二分查找，在0到y之间查找
        b1, b2 = 0, y
        while True:
            x = (b1 + b2) / 2
            if pow1(x, n) < y - 1e-2:
                b1 = x
            elif pow1(x, n) > y + 1e-2:
                b2 = x
            else:
                break
        return [x,-x]
```

【算法题目】浮点数的 n次方根 n次方 ，牛顿迭代法

#   1  题目




```
72. 编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
提示：
0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成
```

#   2  理解 题解

涉及到字符串的题目，十有八九是动态规划，而且几乎都是二维的。解决动态规划问题三要素：

（1）找出dp[] 元素的定义，题目一般非常隐晦。

（2）找出递推关系。dp[n] = $f($ dp[n-1] $)$  。 即是 **状态转移方程**。 

（3）找出初始状态。

编辑距离的题解理解：

（1）将编辑理解到位，简化为在单词 A 中插入一个字符、在单词 B 中插入一个字符、修改单词 A 的一个字符。

（2）由空字符串开头给初始状态。

（3）找出了状态转移方程。

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

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

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

#   3 程序

只要有状态转移方程，动态规划的程序好写：

注意，dp比word长度多1，因为dp里面存着初始数值。
```python
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        if not len(word1) * len(word2):
            return len(word1) + len(word2)
        # 初始状态
        dp = [[0 for _ in range(len(word1) + 1)] for _ in range(len(word2) + 1)]
        dp[0] = [i for i in range(len(word1) + 1)]
        for i in range(len(word2) + 1):
            dp[i][0] = i
        # 状态转移方程计算其余的状态
        for m in range(len(word2)):  # 每一行
            for n in range(len(word1)):  # 每一列
                i = m + 1
                j = n + 1
                # dp[i - 1][j]+1 在word1中插入一个变成word2
                # dp[i - 1][j]+1 在word2中插入一个变成word1
                # dp[i - 1][j - 1]+1 在word1中修改一个变成word2
                if word1[n] == word2[m]:
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] - 1)
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
        return dp[-1][-1]
```

【算法题目】【动态规划】字符串 编辑距离

算法刷题





```
322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
```

# DFS 搜索树太深直接超时

```python
from typing import List
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        coins.sort(reverse=True)
        self.coins_num_res = float("inf")
        def dfs(start, coins_num, residue):
            if residue == 0:
                self.coins_num_res = min(self.coins_num_res, coins_num)
                return
            for index in range(start, len(coins)):
                dfs(index + 1, coins_num, residue)  # dfs 路径1， 不选当前的硬币
                if coins[index] > residue:  # 当前的硬币选了后钱会多，剪枝
                    continue
                # 剪枝，coins_num_res 有结果。
                # 剪枝了也会超时
                if self.coins_num_res != float("inf") and (self.coins_num_res - coins_num) * coins[start] < residue:
                    break
                dfs(index, coins_num + 1, residue - coins[index])  # # dfs 路径2， 选上当前的硬币
        dfs(0, 0, amount)
        return self.coins_num_res if self.coins_num_res != float("inf") else -1
print(Solution().coinChange([1, 2, 5], 11))
# print(Solution().coinChange([411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422], 9864))
```

# BFS 最快的

构建BFS搜索必然借助deque，但是deque里面装什么，怎么搜，始终不太好想象：
```python
from typing import List
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        from collections import deque
        queue = deque([amount])
        step = 0
        visited = set()
        while queue:
            n = len(queue)
            for _ in range(n):  # 本轮选择硬币
                residue = queue.pop()
                if residue == 0:
                    return step
                for coin in coins:
                    # residue >= coin 是停止条件
                    # (residue - coin) not in visited 是剪枝
                    if residue >= coin and (residue - coin) not in visited:
                        visited.add(residue - coin)
                        queue.appendleft(residue - coin)
            step += 1
        return -1
print(Solution().coinChange([411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422], 9864)) # 3万多次循环
```

# 动态规划

```python
class Solution1:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1
```

【算法题目】DFS BFS 动态规划 零钱兑换 Python

算法刷题





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