编程完成动态规划法求解最优二叉搜索树 1 随机化查找数字及其查找成功概率，求出最优二叉搜索树。 2 分析求解的过程并且解释说明。（用python解决上述问题）

### 回答1：
以下是使用 Python 实现动态规划法求解最优二叉搜索树的代码：

import numpy as np

def optimal_bst(p, q, n):
    # 初始化动态规划数组
    e = np.zeros((n+1, n+1))
    w = np.zeros((n+1, n+1))
    root = np.zeros((n, n))

    for i in range(n+1):
        e[i][i-1] = q[i-1]
        w[i][i-1] = q[i-1]

    for l in range(1, n+1):
        for i in range(n-l+1):
            j = i + l - 1
            e[i][j] = float('inf')
            w[i][j] = w[i][j-1] + p[j] + q[j]

            for r in range(i, j+1):
                t = e[i][r-1] + e[r+1][j] + w[i][j]
                if t < e[i][j]:
                    e[i][j] = t
                    root[i][j-1] = r

    return e[0][n-1], root

# 测试代码
p = [0.15, 0.10, 0.05, 0.10, 0.20]
q = [0.05, 0.10, 0.05, 0.05, 0.05, 0.10]
n = len(p)
cost, root = optimal_bst(p, q, n)
print("The minimum cost of optimal binary search tree is:", cost)
print("The optimal binary search tree is:")
print(root)

这个程序使用动态规划算法求解最优二叉搜索树的成本和根节点。输入参数 `p` 表示查找关键字的概率，`q` 表示未找到关键字的概率，`n` 表示关键字的数量。

具体实现步骤如下：

1. 初始化动规数组 $e$ 和 $w$，其中 $e_{i,j}$ 表示从 $i$ 到 $j$ 的最小成本，$w_{i,j}$ 表示从 $i$ 到 $j$ 的概率和。
2. 遍历数组，计算 $e_{i,j}$ 和 $w_{i,j}$，并计算每个可能的根节点 $r$ 的成本。
3. 返回 $e_{0,n-1}$ 和根节点数组。

这个程序的时间复杂度为 $O(n^3)$，空间复杂度为 $O(n^2)$。

### 回答2：
在编程中，我们可以使用动态规划来求解最优二叉搜索树的问题。首先需要随机产生一组数字以及对应的查找成功概率。然后，根据这些数字构建二叉搜索树，并计算出对应的查找成功概率。

具体步骤如下：

1. 随机化产生一组数字以及对应的查找成功概率。假设有 n 个数字，分别为 nums1, nums2, ..., numsn，对应的查找成功概率为 p1, p2, ..., pn。通过这些数字和概率，我们可以构建一棵二叉搜索树。

2. 使用动态规划来求解最优二叉搜索树。定义一个二维数组 dp，其中 dp[i][j] 表示从第 i 个数字到第 j 个数字构建的二叉搜索树的最小查找代价。

3. 初始化 dp 数组。对于只包含一个数字的情况，即 i=j，dp[i][j]=p[i]。对于其他情况，dp[i][j] 的初始值可以设置为一个较大的值或者无穷大，表示还没有计算得出。

4. 使用动态规划的思路来填充 dp 数组。从小到大遍历 j-i+1，即遍历各种长度的数字序列。对于长度为 len 的序列，分别计算 dp[i][j]：
a. 遍历每个可能的根节点 k，其中 i≤k≤j。
b. 计算左子树的最小代价 sum_left = dp[i][k-1]，右子树的最小代价 sum_right = dp[k+1][j]，以及当前根节点 k 的代价，即所有数字的查找成功概率之和：sum_p = sum(p[i:j+1])。
c. 更新 dp[i][j]，dp[i][j] = min(dp[i][j], sum_left + sum_right + sum_p)。

5. 最终，dp[1][n] 就表示从第一个数字到第 n 个数字构建的最优二叉搜索树的最小查找代价。

在 Python 中，可以通过如下代码实现以上算法：

def optimalBST(nums, probs):
    n = len(nums)
    dp = [[0] * (n+1) for _ in range(n+1)]

    for length in range(1, n+1):
        for i in range(1, n-length+2):
            j = i + length - 1
            dp[i][j] = float("inf")

            sum_p = sum(probs[i-1:j])
            for k in range(i, j+1):
                sum_left = dp[i][k-1]
                sum_right = dp[k+1][j]
                dp[i][j] = min(dp[i][j], sum_left + sum_right + sum_p)

    return dp[1][n]

以上就是使用动态规划法求解最优二叉搜索树的过程以及简单的 Python 实现。

### 回答3：
1. 首先，我们需要随机生成一组数字及其对应的查找成功概率。假设有n个数字，我们将数字存储在列表中，对应的查找成功概率存储在另一个列表中。可以使用random库中的random函数生成随机数来生成数字，再使用random函数生成随机概率。

import random

n = 10  # 假设有10个数字
numbers = [random.randint(1, 100) for _ in range(n)]
probabilities = [random.random() for _ in range(n)]

2. 接着，我们需要编写动态规划算法来求解最优二叉搜索树。假设dp[i][j]表示以数字i到j范围内的数字构成的子树的最优二叉搜索树的期望搜索代价。我们可以使用一个二维数组dp来存储这些最优值。

dp = [[0] * n for _ in range(n)]

for l in range(1, n + 1):
    for i in range(0, n - l + 1):
        j = i + l - 1
        for k in range(i, j + 1):
            if k == i:
                dp[i][j] = probabilities[k] + dp[k + 1][j]
            elif k == j:
                dp[i][j] = probabilities[k] + dp[i][k - 1]
            else:
                dp[i][j] = min(dp[i][j], probabilities[k] + dp[i][k - 1] + dp[k + 1][j])

3. 最后，通过调用函数，我们可以输出最优二叉树的期望搜索代价。

def optimal_bst(numbers, probabilities):
    n = len(numbers)
    dp = [[0] * n for _ in range(n)]

    for l in range(1, n + 1):
        for i in range(0, n - l + 1):
            j = i + l - 1
            for k in range(i, j + 1):
                if k == i:
                    dp[i][j] = probabilities[k] + dp[k + 1][j]
                elif k == j:
                    dp[i][j] = probabilities[k] + dp[i][k - 1]
                else:
                    dp[i][j] = min(dp[i][j], probabilities[k] + dp[i][k - 1] + dp[k + 1][j])

    return dp[0][n - 1]

result = optimal_bst(numbers, probabilities)
print(result)

通过以上编程实现，我们可以得到最优二叉搜索树的期望搜索代价。实际运行时，可以根据具体问题的规模调整参数n，并在随机生成数字及其查找成功概率时设置合适的取值范围。