使用动态规划写一个监控二叉树

监控二叉树问题可以使用动态规划来解决。具体思路如下：

1. 定义状态：使用一个三元组 (u, 0/1, 0/1) 表示当前节点 u 的状态，其中第二个元素表示 u 是否被监控，第三个元素表示 u 的父节点是否被监控。

2. 定义转移：对于一个节点 u，假设其左右子节点分别为 v 和 w，可以分为以下三种情况：

a) u 被监控：则 v 和 w 都必须被监控，转移方程为 dp[u][1][0] = dp[v][0][1] + dp[w][0][1] + 1。

b) u 未被监控且其父节点被监控：则 v 和 w 中至少有一个被监控，转移方程为 dp[u][0][1] = min(dp[v][1][0] + dp[w][1][0], dp[v][0][1] + dp[w][1][0], dp[v][1][0] + dp[w][0][1])。

c) u 未被监控且其父节点未被监控：则 v 和 w 中至少有一个被监控，转移方程为 dp[u][0][0] = min(dp[v][1][0] + dp[w][1][0], dp[v][0][1] + dp[w][1][0], dp[v][1][0] + dp[w][0][1], dp[v][0][0] + dp[w][0][0])。

3. 初始状态：对于叶子节点，dp[u][0][0] = 0, dp[u][1][0] = 1, dp[u][0][1] = INF，INF 表示一个足够大的值。

4. 最终答案：对于根节点，dp[root][0][1] 和 dp[root][1][0] 中的较小值即为所求。

下面是使用 Python 代码实现：

INF = float('inf')

def dfs(u, fa, dp):
    if not u:
        return
    dfs(u.left, u, dp)
    dfs(u.right, u, dp)

    dp[u][1][0] = dp[u.left][0][1] + dp[u.right][0][1] + 1
    dp[u][0][1] = min(dp[u.left][1][0] + dp[u.right][1][0], dp[u.left][0][1] + dp[u.right][1][0], dp[u.left][1][0] + dp[u.right][0][1])
    dp[u][0][0] = min(dp[u.left][1][0] + dp[u.right][1][0], dp[u.left][0][1] + dp[u.right][1][0], dp[u.left][1][0] + dp[u.right][0][1], dp[u.left][0][0] + dp[u.right][0][0])

    if fa:
        dp[u][1][1] = dp[u][0][0] + 1
        dp[u][0][1] = min(dp[u][0][1], dp[u][1][0])
    else:
        dp[u][1][1] = dp[u][0][0] + 1

def min_camera_cover(root):
    dp = {}
    dfs(root, None, dp)
    return min(dp[root][1][0], dp[root][0][1])

其中，root 表示根节点，dp 是一个字典，dp[u][i][j] 表示节点 u 的状态为 (u, i, j) 时的最小监控数。