动态规划实例：最长公共子序列与数字三角形和求解

"最长公共子序列-动态规划案例" 在这个主题中，我们讨论的是一个经典的计算机科学问题——最长公共子序列（Longest Common Subsequence, LCS），通常使用动态规划算法来解决。动态规划是一种将复杂问题分解成更小子问题并存储解决方案以避免重复计算的技术。在给定的序列X和Y中，我们需要找到它们共享的最长子序列，这个子序列不一定要连续，但必须是两个输入序列中都有的。 问题描述中，定义了子序列的概念，即一个序列是另一个序列的子序列，只要存在一种方式，使得子序列中的每个元素都能在原序列中找到对应的位置。例如，对于序列X="abcdfbc"和Y="abcdefg"，最长公共子序列是"abc"。 针对最长公共子序列问题，动态规划的思路是创建一个二维数组，其中每个元素表示两个子序列的前缀部分的最大公共子序列长度。通过比较子序列X和Y中相应位置的字符，决定是保留当前字符还是跳过，从而逐步填充这个数组，最终找到整个序列的最大公共子序列长度。 而在数字三角形问题中，给定一个具有递归结构的三角形，目标是找出从顶点到底部的最佳路径，即路径上数字之和最大。该问题同样可以用动态规划解决，通过定义状态变量MaxSum(r,j)来记录到达第r行第j个数字时的路径和。递归地计算以当前数字为起点的两种可能路径的和，取较大者作为当前状态的最优值，直到到达底行。 参考程序展示了如何用C语言实现这个算法。首先读取输入的三角形大小和数字，然后使用MaxSum函数递归地计算从给定位置向下走的最优路径和。主函数中，通过输入循环读取三角形的数据，最后输出最大和。 总结来说，这两个案例均体现了动态规划在解决序列相关问题中的威力，通过将大问题分解为更小的子问题，并存储中间结果，有效地减少了计算量，提高了效率。理解并掌握动态规划在这些问题中的应用，对于提高编程技能和解决实际问题具有重要意义。