下面哪些具有最优子结构性质()A. 最短路径问题B. 最长公共子序列问题C. 最长简单路径问题D. 矩阵连乘问题

最优子结构的定义是：问题的最优解包含其子问题的最优解。判断一个问题是是否具有最优子结构，需要验证原问题的最优解是否由其子问题的最优解组合而成。

• 关键点：若原问题的最优解确定后，其子问题的最优解必须被包含在其中，并且这些子问题的最优解的组合能形成原问题的最优解。
• 常见问题类型：动态规划和贪心算法通常依赖最优子结构。例如，最短路径、最长公共子序列、矩阵连乘等具有此性质，而最长简单路径通常不具有。

A. 最短路径问题

分析：假设从顶点 $s$ 到 $t$ 的最短路径经过顶点 $u$，则该路径可分解为 $s \to u$ 的最短路径和 $u \to t$ 的最短路径。子问题的最优解（$s \to u$ 和 $u \to t$）组合后形成原问题的最优解，因此具有最优子结构。

B. 最长公共子序列问题

分析：设两个序列 $X$ 和 $Y$ 的最长公共子序列（LCS）长度为 $c$。若 $X$ 的最后一个字符 $X[i]$ 等于 $Y$ 的最后一个字符 $Y[j]$，则 $c = LCS(X_{i-1}, Y_{j-1}) + 1$；否则，$c = \max(LCS(X_{i-1}, Y), LCS(X, Y_{j-1}))$。子问题的最优解（前缀的LCS）被包含在原问题的最优解中，因此具有最优子结构。

C. 最长简单路径问题

分析：最长简单路径是无重复顶点的路径。假设从 $s$ 到 $t$ 的最长路径经过顶点 $u$，可能存在另一条不经过 $u$ 的路径更长。子问题的最优解（$s \to u$ 和 $u \to t$）未必组合成原问题的最优解，因此不具有最优子结构。

D. 矩阵连乘问题

分析：矩阵连乘 $A_1A_2\cdots A_n$ 的最优计算方式必存在一个拆分点 $k$，使得前 $k$ 个矩阵和后 $n-k$ 个矩阵的最优计算方式组合成整体最优。子问题的最优解（前缀和后缀的最优计算）被包含在原问题的最优解中，因此具有最优子结构。