![在这里插入图片描述](/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 括号生成

我是一个专注技术分享的博主,尤其爱搞深度学习和单片机电子。你现在看到的是我的个人博客网站。