湘潭大学软件工程算法设计与分析考试复习笔记（三）

回顾

• 湘潭大学软件工程算法设计与分析考试复习笔记（一）
• 湘潭大学软件工程算法设计与分析考试复习笔记（二）

前言

现在继续开始复习。每天复习一点点，嘿嘿。今天本来准备写一个动态规划的题的，感觉半懂不懂的，看了一个网友半年拿下什么很厉害的奖，看得我热血沸腾，有一种我上我也行的幻觉。但是现在我又冷静下来了。我得先复习一下期末考试。

动态规划

基本思想

给我的感觉就是把一些状态记录在数组里面，课件上面写了动态规划和贪心的一些区别，感觉记一下比较好。不过我对这个理解不是很深刻。

动态规划简称 DP ，

矩阵连乘

这里有一个算法时间复杂度的表示符号，笔者在这里有点想要卖弄一下了，哈哈哈。这个符号表示的是时间复杂度的下界。

下面这个时间复杂度的符号表示的是对时间复杂度的准确估计

下面这个时间复杂度的符号表示的是时间复杂度的上界

这种完全看不懂，太难了。

多边形游戏

这个也好难。记一记时间复杂度先。

最长公共子序列

#include<bits/stdc++.h>

using namespace std;

const int N=1e3+10;

char a[N],b[N];
int f[N][N];

int main()
{
    int n,m;
    cin>>n>>m>>(a+1)>>(b+1);

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i]==b[j])  f[i][j]=max(f[i][j],f[i-1][j-1]+1);
        }
    }

    cout<<f[n][m]<<endl;

    return 0;
}

哈哈哈，这里建议读者在网上找这个算法题来写，我之前写过，现在感觉忘了。看课件应该直接看懂比较艰难。可以搜一些视频看看。

总结

课件里面的这些内容好像是算法竞赛里面的内容。比较难。可能是我们学那种比较简单直观的专业课比较多，现在看到这种强逻辑性的知识，都看不下去。真难。

其他的我都看不懂，我记一下下面这个总结。

后记

第一个题型，对算法的基本理解，就复习结束了，但是把课件粗略地看了一遍，4 5 7 这三章课件。总共是 8 章课件，感觉像我这样看课件也不太行，得仔细看课件，但是也记不住，理解不了，纠结。明天继续按照题型复习好了。10 分。

今天复习算法的时间有点少，但是做了一些我感觉很有价值的事情，血赚。虽然不知道是不是真的有价值，应该是有价值吧，但行好事，不问前程。