动态规划（1）——最长子序列（LCS）问题

最长子序列问题：从中找出最长的字符序列，比如： cnblogs和belong。这两个字符串的最长子序列就是blog。

动态规划：通过分解大问题，不断的将大问题变成小问题，最终整合所有解，得出最优解（和递归有点相似，但是递归的时间复杂度太过大，通过动态规划的解决，可以将一部分的时间复杂度调整成空间复杂度）

X_m = {x₁，x₂，x₃...x_m}，Y_n = {y₁，y₂，y₃，...y_n}，求X和Y的最长子序列。

1，假设Z = {z₁，z₂，...， z_k}是X和Y的最长子序列，那么可以看出（解1）

• 如果x_m = y_n ，那么Z_k-1 就是X_m-1和Y_n-1的LCS（因为最后一个元素相等且已经规定Z_k是X_m和Y_n的LCS，所以Z_k-1 自然就是X_m-1和Y_n-1的LCS）
• 如果x_m ≠ y_n ，那么有Z_k = {X_m-1，Y_n}的LCS或者Z_k = {X_m，Y_n-1}的LCS（因为X和Y的最后一个元素不相同，所以自然最后一个元素不在LCS序列中，但是并不知道到底是哪个字符串不存在于序列中，所以这里拆分成了两个子问题）

所以通过上面的分析，可以得出状态转移方程（该方程记录的是所有状态改变的过程，即记录每个状态的过程，通过二维数组记录）

c[i,j] =   1.  0       　　　　　　　　　　　　i=0 || j =0

  　　　2.  c[i-1,j-1] +1     　　　　　　　　i > 0 and j > 0 and x_i = y_j

　　　  3.  Math.Max(c[i-1,j],c[i,j-1])     　　 i > 0 and j > 0 and x_i ≠ y_j

（解释2：即始终保存的是目前最长的子串长度，通过解1的第一点可以看出如果最后一个元素相同那么LCS就是两个字符串长度-1的LCS，由于原问题比较庞大，所以现在是通过拆分原问题将它变成很多小问题来解决；解释3：同参考解释2和解1的第二点）

状态转移表如下表显示：

			i
			1	2	3	4	5	6	7
			c	n	b	l	o	g	s
j	1	b	0	0	1	1	1	1	1
	2	e	0	0	1	1	1	1	1
	3	l	0	0	1	2	2	2	2
	4	o	0	0	1	2	3	3	3
	5	n	0	1	1	2	3	3	3
	6	g	0	1	1	2	3	4	4

代码如下：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        public static int[,] flag = new int[8,7];
        public static string str1 = "cnblogs";
        public static string str2 = "belong";
        static void Main(string[] args)
        {
            
            int[,] c = Lcs(str1, str2);
            for (int i = 0;i<str1.Length+1;++i)
            {
                for(int j= 0;j<str2.Length+1;++j)
                {
                    Console.Write(c[i, j]);
                }
                Console.Write("\n");
            }
            Console.WriteLine("输出LCS序列");
            printLcs(str1.Length,str2.Length);
            Console.ReadKey();
        }

        public static void printLcs(int i,int j)
        {
            if (i == 0 || j == 0) return;
            if (flag[i, j] == 0)
            {
                //Console.Write(str1[i - 1]);
                printLcs(i - 1, j - 1);
                Console.Write(str1[i - 1]);

            }
            else if (flag[i, j] == 1)
            {
                printLcs(i - 1, j);

            }
            else
                printLcs(i, j - 1);
        }

        public static int[,] Lcs(string str1, string str2)
        {
            int len1 = str1.Length+1;
            int len2 = str2.Length+1;
            int[,] c = new int[len1, len2];
            string[] sc = new string[Math.Max(len1, len2)];
            for(int i = 0;i<len1;i++)
            {
                for(int j =0;j<len2;j++)
                {
                    if (i == 0 || j == 0)
                        c[i, j] = 0;
                    else if (str1[i - 1] == str2[j - 1])
                    {
                        c[i, j] = c[i - 1, j - 1] + 1;
                        flag[i, j] = 0;
                    }
                    else
                    {
                        c[i, j] = Math.Max(c[i, j - 1], c[i - 1, j]);
                        if (c[i, j - 1] <= c[i - 1, j])
                            flag[i, j] = 1;
                        else
                            flag[i, j] = -1;
                    }
                }
            }
            for(int i = 0;i<8;++i)
            {
                for(int j=0;j<7;++j)
                {
                    Console.Write(flag[i, j] + "   ");
                }
                Console.Write("\n");
            }
            return c;
        }
    }
}

其中，完成状态转移的片段如下

int len1 = str1.Length+1;
            int len2 = str2.Length+1;
            int[,] c = new int[len1, len2];
            string[] sc = new string[Math.Max(len1, len2)];
            for(int i = 0;i<len1;i++)
            {
                for(int j =0;j<len2;j++)
                {
                    if (i == 0 || j == 0)
                        c[i, j] = 0;
                    else if (str1[i - 1] == str2[j - 1])
                    {
                        c[i, j] = c[i - 1, j - 1] + 1;
                        flag[i, j] = 0;
                    }
                    else
                    {
                        c[i, j] = Math.Max(c[i, j - 1], c[i - 1, j]);
                        if (c[i, j - 1] <= c[i - 1, j])
                            flag[i, j] = 1;
                        else
                            flag[i, j] = -1;
                    }
                }
            }

注：该片段代码只提供状态转移的过程和该问题的最长子序列的长度，若需要确定LCS的元素，则需要通过另外一个数组保存状态转移的信息（即该状态是从何而来，是从哪个数据继承过来的）；flag数组代表的就是状态转移的信息，这里分成三种情况，代表着当前状态的来源，分别是：c[i-1,j-1]、c[i-1,j]、c[i,j-1]。

实现代码如下：

 public static void printLcs(int i,int j)
        {
            if (i == 0 || j == 0) return;
            if (flag[i, j] == 0)
            {
                //Console.Write(str1[i - 1]);
                printLcs(i - 1, j - 1);
                Console.Write(str1[i - 1]);

            }
            else if (flag[i, j] == 1)
            {
                printLcs(i - 1, j);

            }
            else
                printLcs(i, j - 1);
        }

该问题通过保存状态转移的信息，然后再利用递归的方法得出结果。

代码解读：第一个  if 中，判断传入的 i 与 j  （i 和 j  代表存储状态转移信息的数组的下标），倘若所有数据已经遍历完毕，那么终止递归；第二个 if 中，如果flag中保存的数据 == 0 则表示当前数据来自于 c[i-1,j-1] 所以此时递归参数就是 i-1 和 j-1，而 else if 和 else 也相应的代表另外两个来源方向。

注：由于该方法是从后到前的递归，所以Console要在函数后面，意味着先递归再输出，那么输出的结果就是从头开始，加入先输出再递归的话，那么输出的结果就是刚好相反的，比如正确的结果是 blog，那么由于错误的输出方式则造成了现在的结果是 golb。

为什么选择从后往前递归呢？第一点当然是为了方便，大家都习惯于将递归的结束条件写成与0有关，第二点是因为该数据状态的继承是从前面的数据得到的，而不是从后面的数据得到的，所以只有后面的数据可以找到前面的数据，而前面的无法预知后面的。（我猜是这样的！）

最后一点：动态规划中最重要的一步是写出该问题的状态转移方程，将问题划分成若干子问题；最核心的一步是知道要用动态规划（这不是废话吗！通常碰到类似于递归，分治的，如果不可行或者时间复杂度过于庞大的话就要考虑动态规划了）