[ 算法 ] 最长公共子序列

问题

矩阵是按行和列排列的数字集合。矩阵A（r行s列）和矩阵B（p行q列）能够相乘的条件为s=p，即前一个矩阵的列数要等于后一个矩阵的行数。完成乘法AB共需要r_s_q次乘法。举证乘法满足结合律，但不满足交换律，即一般情况下AB和BA并不相等，但(AB)C和A(BC)的结果是一样的。现有n个矩阵连乘，记为A_1A_2...A_nA1A2...An，A_1A1的行列分别为p_0p0和p_1p1，A_2A2的行列为p_1p1和p_2p2，以此类推。请设计算法，给出矩阵连乘的顺序，使总计算量最小。总计算量为每次矩阵相乘的乘法次数之和。

输入

第一行为一个数n。第二行为n个数，分别为p1,...,pn。

输出

编码所需要的最少位数。

代码

#define _CRT_SECURE_NO_WARNINGS
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

char a[1001], b[1001];
int dp[1001][1001], len1, len2;

void lcs(int i, int j)
{
    //第一个序列
    for (i = 1; i <= len1; i++)
    {
        //第二个序列
        for (j = 1; j <= len2; j++)
        {

            if (a[i - 1] == b[j - 1])//存在相同子序
                dp[i][j] = dp[i - 1][j - 1] + 1; //存入子序长度
            //上一个状态自序长度大于当前自序长度则保持上一个状态的子序长度不变
            else if (dp[i - 1][j] > dp[i][j - 1])
                dp[i][j] = dp[i - 1][j]; //保持上一个状态的序列长度
            else
                //当前状态的子序长度大于上一次状态子序长度
                dp[i][j] = dp[i][j - 1]; //填入当前自序长度
        }
    }
}

int main()
{
    while (~scanf(" %s", a))
    {
        scanf(" %s", b);
        memset(dp, 0, sizeof(dp));
        len1 = strlen(a); //第一个字符串序列长度
        len2 = strlen(b); //第二个字符串序列长度

        lcs(len1, len2);
        printf("%d\n", dp[len1][len2]);
    }
    return 0;
}