【算法导论之七】动态规划求解最长公共子序列

一、动态规划的概念

        动态规划（Dynamic Programming）是通过组合子问题的解而解决整个问题的。分治算法是指将问题划分成一些独立的子问题，递归地求解各子问题，然后合并子问题的解而得到原始问题的解，与此不同，动态规划适用于子问题不是独立的情况，也就是各个子问题包含公共的子问题。在这种情况下，采用分治法会做许多不必要的工作，即重复地求解公共地子问题。动态规划算法对每个子问题只求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案。

        动态规划通常应用于最优化问题。此类问题可能有很多种可行解。每个解有一个值，而我们希望找出具有最优（最大或最小）值的解。称这样的解为该问题的“一个”最优解，而不是“确定的”最优解，因为可能存在多个取最优值的解。

        为了节约重复求相同子问题的时间，引入一个数组，不管他们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划所采用的基本方法。

二、动态规划求解的一般步骤

        动态规划算法的设计可以分为如下4个步骤：

        1> 描述最优解的结构。

        2> 递归定义最优解的值。

        3> 按自底向上的方式计算最优解的值。

        4> 由计算出的结果构造一个最优解。

        这就是动态规划算法的一般步骤，单这么说肯定没有任何意义，下面我们会通过求解最长公共子序列问题来说明，如何一步步的适用动态规划思想分析问题。

三、最长公共子序列问题描述

        问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列 X = "x0, x1, ... xm-1"，字符序列 Y = "y0, y1, ... , yk-1"是X的子序列，则存在X的一个严格递增（注意：不是连续递增）下标序列<i0, i1, ... , ik-1>，使得对所有的j=1=0, 1, ... , k-1，有xj = yj。例如，X="ABCBDAB", Y="BCDB"是X的一个子序列。

        先给出问题：假设字符串X = “ABCBDAB”， Y=“BDCABA”，求他们的最长公共子序列。

四、动态规划求解最长公共子序列问题

        1> 描述最优解的结构。

              解决上述问题的一种强力方法是枚举出X的所有子序列，然后逐一检查看其是否为Y的子序列，并随时记录所发现的最长子序列。X的每个子序列对应于X的下标集{1，2，... ，m}的一个子集。X共有2^m个子序列，因此这种方法需要指数时间，这对长序列来说是不实际的。

              设 X = <x1, x2, ... , xm> 和 Y = <y1, y2, ... , yn>为两个序列，并设Z = <z1, z2, ... , zk>为X和Y的任意一个最长公共子序列。则我们可以得出以下的结论：

              1) 如果Xm = Yn，那么zk = Xm = Yn，而且zk-1是Xm-1和Yn-1的一个最长公共子序列。

              2) 如果Xm != Yn，那么zk != Xm蕴含Z是Xm-1和Yn的一个最长公共子序列。

              3) 如果Xm != Yn，那么zk != Yn蕴含Z是Xm和Yn-1的一个最长公共子序列。

             这样，在找X和Y的最长公共子序列时，如果有Xm-1 = Yn-1，则进一步解决一个子问题，找"x0, x1, ... , xm-2" 和 "y0, y1, ... , yn-2"的一个最长公共子序列；如果Xm-1 != Yn-1，则需要解决两个子问题，找出"x0, x1, ... , xm-2" 和 "y0, y1, ... , yn-1"的一个最长公共子序列和找出 "x0, x1, ... , xm-1" 和 “y0, y1, ... , yn-2”的一个最长公共子序列，再去两者中较长者作为X和Y的最长公共子序列。

        2> 递归定义最优解的值

              最长公共子序列问题的递归解涉及到建立一个最优解的递归式。定义c[i, j]的序列为Xi 和 Yj的一个最长公共子序列的长度。如果i = 0 或 j = 0，其中一个的序列长度为0，因此最长公共子序列的长度为0。由最长公共子序列问题的最优子结构可得递归式

        3> 按自底向上的方式计算最优解的值      

              引入一个二维数组，C[i][j]，用C[i][j]记录X[i]与Y[j]的最长公共子序列的长度，B[i][j]记录C[i][j]是通过那一个子问题的值求得的，以决定搜索我们是自底向上进行递推计算，那么在计算c[i,j]之前，c[i-1][j-1]，c[i-1][j]与c[i][j-1]均已计算出来。此时我们根据X[i] = Y[j]还是X[i] != Y[j]，就可以计算出c[i][j]。      

for (int i = 1; i <= nXlen; i++)
	{
		for (int j = 1; j <= nYlen; j++)
		{
			if (strX[i] == strY[j])
			{
				C[i][j] = C[i-1][j-1] + 1;
				B[i][j] = 0;
			}
			else
			{
				//! 注意这里的=号，它表示了，如果C[i-1][j] == C[i][j-1]的时候，它既可以向左走又可以向上走
				//! 而此时选择了向左走，按照此种方式输出最长公共子序列的时候，只能输出一条，需改进！！
				<span style="color:#FF0000;">if (C[i-1][j] >= C[i][j-1])</span>
				{
					C[i][j] = C[i-1][j];
					B[i][j] = 1;   //! 左移
				}
				else
				{
					C[i][j] = C[i][j-1];
					B[i][j] = -1; //! 右移
				}
			}
		}
	}

void PrintAllCase(int B[][MAX_LEN], const string &strX, int i, int j)
{
	if (i == 0 || j == 0)
	{
		return ;
	}

	if (B[i][j] == 0)
	{
		PrintAllCase(B, strX, i-1, j-1);
		cout << strX[i-1];
	}
	else if (B[i][j] == 1)
	{
		PrintAllCase(B, strX, i-1, j);
	}
	else
	{
		PrintAllCase(B, strX, i, j-1);
	}
}

五、C++实现代码

/************************************************************************/
/* 动态规划求解最长公共子序列                                           */
/************************************************************************/
#include <stdlib.h>
#include <iostream>
#include <string>
using namespace std;

#define  MAX_LEN     100
void LCS(const string &strX, const string &strY, int nXlen, int nYlen, int C[][MAX_LEN], int B[][MAX_LEN])
{
	for (int i = 0; i <= nXlen; i++)
	{
		C[i][0] = 0;
	}

	for (int j = 0 ; j <= nYlen; j++)
	{
		C[0][j] = 0;
	}

	for (int i = 1; i <= nXlen; i++)
	{
		for (int j = 1; j <= nYlen; j++)
		{
			if (strX[i] == strY[j])
			{
				C[i][j] = C[i-1][j-1] + 1;
				B[i][j] = 0;
			}
			else
			{
				//! 注意这里的=号，它表示了，如果C[i-1][j] == C[i][j-1]的时候，它既可以向左走又可以向上走
				//! 而此时选择了向左走，按照此种方式输出最长公共子序列的时候，只能输出一条，需改进！！
				if (C[i-1][j] >= C[i][j-1])
				{
					C[i][j] = C[i-1][j];
					B[i][j] = 1;   //! 左移
				}
				else
				{
					C[i][j] = C[i][j-1];
					B[i][j] = -1; //! 右移
				}
			}
		}
	}
}

void PrintAllCase(int B[][MAX_LEN], const string &strX, int i, int j)
{
	if (i == 0 || j == 0)
	{
		return ;
	}

	if (B[i][j] == 0)
	{
		PrintAllCase(B, strX, i-1, j-1);
		cout << strX[i-1];
	}
	else if (B[i][j] == 1)
	{
		PrintAllCase(B, strX, i-1, j);
	}
	else
	{
		PrintAllCase(B, strX, i, j-1);
	}
}

int main()
{
	string strX = "ABCBDAB";
	string strY = "BDCABA";
	
	int C[MAX_LEN][MAX_LEN];    //! 记录最长公共子序列的长度
	int B[MAX_LEN][MAX_LEN];    //! 记录最长公共子序列的移动线路

	int nXlen = strX.length();
	int nYlen = strY.length();

	LCS(strX, strY, nXlen, nYlen, C, B);
	cout << "The max length of LCS is " << C[nXlen][nYlen] << endl;

	cout << "The LCS are : ";
	PrintAllCase(B, strX, nXlen, nYlen);

	system("PAUSE");
	return 0;
}

当前算法实现在输出最长公共子序列的时候只能输出一条，如果需要输出所有的则需要改进。

原文：http://blog.csdn.net/houqd2012/article/details/39928159