动态规划：子问题递归与最长公共子序列

动态规划是一种在计算机科学中用于解决最优化问题的算法方法，特别适用于那些具有重叠子问题和最优子结构的问题。在这个特定的讲义中，我们关注的是子问题的递归结构在动态规划中的应用，以解决最长公共子序列（Longest Common Subsequence, LCS）问题。 LCS问题是指找到两个序列中最长的共同子序列，而子问题的递归结构则是通过定义一个二维数组c[i][j]来表示序列X={x1, x2, ..., xi}和序列Y={y1, y2, ..., yj}的最长公共子序列的长度。递归结构的关键在于理解两个边界情况：当i或j为0时，由于序列为空，空序列自然是它们的最长公共子序列，所以c[i][j]的值为0。对于其他非边界情况，根据最优子结构性质，即子问题的最优解可以通过较小规模子问题的最优解组合得出，可以建立如下的递归关系： c[i][j] = - 如果 xi = yj，则c[i][j] = c[i-1][j-1] + 1（因为当前元素相同，子序列长度加1） - 否则，c[i][j] = max(c[i-1][j], c[i][j-1]) （取不包含当前元素的最长子序列） 举例来说，对于给定的两个序列A和B，动态规划过程会填充一个二维表，每一步比较当前元素是否匹配，然后根据最优子结构选择保留当前元素或不保留，以求得最大公共子序列的长度。在填表过程中，不仅记录了长度，还间接地找到了最长公共子序列的具体序列。 此外，讲义还提到了0-1背包问题，这是另一个典型的动态规划问题。在0-1背包问题中，目标是在给定的背包容量限制下，选择物品以最大化总价值。同样利用最优子结构，我们可以建立一个递归公式来计算背包容量为j时，前i个物品能装入背包的最大价值m(i, j)。 这个讲义深入剖析了如何通过子问题的递归结构和动态规划的思想来解决LCS问题以及0-1背包问题，展示了动态规划算法的强大实用性。理解和掌握这些递归关系和方法，是学习和运用动态规划解决问题的基础。