LCS属线性结构上的动态规划，应该是动规里面很简单的一种类型。

最长公共子序列问题，一旦明确了状态，找到状态转移方程还是很简单的。但是对于本题来说，难点之一就是会很难想到该如何定义状态。

作为一只菜鸟，兹认为此题很复杂。

首先我是想不到每一步都把没到终点的字母全加上1，以及这种效果与你去找开始和结束的效果是一样的。

甚至，若不是在做动规的专题，我根本想不到这样的题目，会用动规来解决。

再一个，我想不到状态可以这么来定义“设d[ i ][ j ]表示两个序列分别已经拿出去了 i 个和 j 个元素 ”。其值代表的是当前状态的最小L值。

再一个我很难相信自己能完成前期对cnt[ i ][ j ]数组的处理，事实上我已经完成了其大半，但是因为对自己的好像是O(n^3)方法没有信心，怯懦的放弃了。

再一个不知道是不是因为对复杂处理的恐惧，在明确了方法之后，写代码的过程中也一直没有清楚的思路，导致在解题过程中很多地方没有处理好，对最后结果造成了巨大的影响，也为最后的debug造成了极大困难，浪费了很多的精力和时间，做了很多的无用功，必须好好反思。

最后虽然明确了状态转移方程，但是在对边界的处理上，思路可谓混乱不堪。简直是在猜测！问问自己这是什么状态？你该猜吗？你连脑子都不转你既然猜那你怎么不去搬砖，你猜个P啊？你就不能静下心来人认真考虑考虑便捷的状态吗？我觉得你肯定能把边界标示清楚，你为什么不肯静下来好好思考思考？必须反思！

环境太乱影响了我，周围的讨论使我浮躁。但是不该对任何一道题目浮躁。

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 0x6fffffff

const int maxn = 5010;
char s1[maxn],s2[maxn];
struct color
{
    int st1,end1;
    int st2,end2;
    int ok;
}co[30];
int cnt[maxn][maxn];
int d[maxn][maxn];

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%s",s1,s2);
        int len1 = strlen(s1);
        int len2 = strlen(s2);

        for(int i=0;i<30;i++)
        {
            co[i].ok=1;
            co[i].st1=co[i].st2=INF;
            co[i].end1=co[i].end2=-INF;
        }
        for(int i=0;i<len1;i++)
        {
            int temp = s1[i]-'A';
            if(co[temp].ok==1)
            {
                co[temp].ok=0;
                co[temp].st1=i;
            }
            co[temp].end1=i;
        }
        for(int i=0;i<30;i++)
        {
            co[i].ok=1;
        }
        for(int i=0;i<len2;i++)
        {
            int temp = s2[i]-'A';
            if(co[temp].ok==1)
            {
                co[temp].ok=0;
                co[temp].st2=i;
            }
            co[temp].end2=i;
        }
        for(int i=0;i<=len1;i++)
        {
            for(int j=0;j<=len2;j++)
            {
                int cnt_=0;
                for(int k=0;k<26;k++)
                {
                    if(co[k].st1==INF&&co[k].st2==INF)
                        continue;
                    if(co[k].st1>i-1&&co[k].st2>j-1)///注意是i-1；(已推理验证，正确)
                        continue;
                    if(co[k].end1<=i-1&&co[k].end2<=j-1)///是小于等于i-1；（已验证，正确）
                        continue;
                    cnt_++;
                }
                cnt[i][j]=cnt_;
            }
        }
        d[len1][len2]=0;
        for(int i=len2-1;i>=0;i--)
        {
            d[len1][i]=d[len1][i+1]+cnt[len1][i];
        }
        for(int i=len1-1;i>=0;i--)
        {
            d[i][len2]=d[i+1][len2]+cnt[i][len2];
        }
        for(int i=len1-1;i>=0;i--)
        {
            for(int j=len2-1;j>=0;j--)
            {
                d[i][j]=min(d[i+1][j],d[i][j+1])+cnt[i][j];
            }
        }
        printf("%d\n",d[0][0]);
    }
    return 0;
}

做题很久了，该静下心，遇到复杂的题目和解决不了的题目也该有自己的态度。烦躁解决不了任何事情，也不会有任何帮助。发泄归发泄，认真对待是最重要的

宁肯不做，也不凑过。

再一个，适当提高对自己能力的肯定，既然有想法与思路，就鼓励自己一定要写完看看~即使超时是不正确，也是对自己代码能力和心智的一种锻炼，有助于代码能力的提高，也有助于增强自己面对复杂题目敢于下手的信念。不怕麻烦，不惧困难。缺少一种 就是干 的精神