C++动态规划解决最长公共子序列问题

编程环境：VS2019。最长公共子序列问题具有前效性，适合采用动态规划方法。对于字符串a的每个字符ai，与字符串b中的所有字符比较。如果发现相等，则当前最长公共子序列为a1,a2...ai-1与b1,b2...bj-1的最长公共子序列加上ai和bj；如果不相等，则当前最长公共子序列为a1,a2...ai-2与b1,b2...bj-1的最长公共子序列，或者a1,a2...ai-1与b1,b2...bj-2的最长公共子序列。这构成了状态转移方程。最终，根据得到的最长公共子序列长度数组，回溯路径即可得到最长公共子序列，结果不唯一。采用二维数组he存放当前状态下的最长公共子序列长度，并根据he数组回溯路径。复杂度分析：时间复杂度为O(nm)，空间复杂度为O(nm)。