数据结构算法——1039. 最长连续公共子序列

假定A的i-1和B的j-1的数据并不相同，比较A的i位置和B的j位置要从0开始累加
若A的i位置和B的j位置相同，那么在比较A的i+1位置和B的j+1位置时候，就要从1开始累加
于是我们不难得出dp条件
a r r a y [ i + 1 ] [ j + 1 ] = a r r a y [ i ] [ j ] + 1 A [ i ] = = B [ i ] array[i+1][j+1]=array[i][j] + 1quad A[i]==B[i]\ array[i+1][j+1]=array[i][j]+1A[i]==B[i]
其他情况array[i+1][j+1]为0

#include
#include
using namespace std;

int main()
{
    string A,B;
    cin >> A >> B;
    short* f = new short[ (A.length()+1) * (B.length()+1)];
    memset(f,0,sizeof(short) * (A.length()+1) * (B.length()+1));
    int max = 0;
    
    	for (int i = 0; i < A.length(); i++) 
        {
			for (int j = 0; j < B.length(); j++) 
            {
				if(A.at(i) == B.at(j))
                {
					f[(i+1) * (B.length() + 1) + j+1] = f[(i)*(B.length()+1) + j]+1;
                    if(f[(i+1) * (B.length() + 1) + j+1] > max)
                        max = f[(i+1) * (B.length()+1) + j+1];
				}
			}
		}
    cout << max;
}

每执行完一次第二层循环的时候，对应的前面部分的array就不会再使用了，我们可以通过mod运算来减少内存的损耗

#include
#include
using namespace std;

int main()
{
    string A,B;
    cin >> A >> B;
    short* f = new short[ (B.length()+1) * 100];
    memset(f,0,sizeof(short) * (B.length()+1) * 100);
    int max = 0;
    
        for (int i = 0; i < A.length(); i++) 
        {
            for (int j = 0; j < B.length(); j++) 
            {
                if(A.at(i) == B.at(j))
                {
                    f[((i + 1) % 100) * (B.length() + 1) + j+1] = f[(i % 100) * (B.length() + 1) + j] + 1;
                    if(f[((i + 1) % 100) * (B.length() + 1) + j+1] > max)
                        max = f[((i + 1) % 100) * (B.length() + 1) + j+1];
                }
                
            }
        }
    cout << max;
}