预处理下连续相等的字符个数其实主要是看是否满3个
后面递推的时候特判下+1上次递推[i-1,j-1]不是来自[i-2,j-1]也不是来自[i-1,j-2]其实就是只来自[i-4,j-4]+3,和[i-2,j-2]+1这样才能保证连续让长度超过3的继续增加1
但是这里不通过直接[i-4,j-4]+3[i-1,j-1]判断因为不满足3的不算进来,比如[0,0]+3[3,3]可以但是[1,1]+3!=[4,4]因为[1,1]也是0,就不能推出[5,5]了,当然也可以用[3,3]+1==[4,4]或判断,不过数组下标-4就又把范围扩大了
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication12
{
class Program
{
public static int[,] dp;
public static int[,] pd;
static void Main(string[] args)
{
string nstr;
string mstr;
nstr = Console.ReadLine();
mstr = Console.ReadLine();
int n = nstr.Length;
int m = mstr.Length;
dp = new int[n, m];
pd = new int[n, m];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (i < 1 || j < 1)
pd[i, j] = (nstr[i] == mstr[j] ? 1 : 0);
else
pd[i, j] = (nstr[i] == mstr[j] ? pd[i - 1, j - 1] + 1 : 0);
for (int i = 2; i < n; i++)
{
for(int j = 2; j < m; j++)
{
if (pd[i, j] >= 3)
{
if (i < 3 || j < 3)
dp[i, j] = 3;
else
dp[i, j] = Math.Max(dp[i, j], dp[i - 3, j - 3] + 3);
}
if(dp[i-1,j-1]!=dp[i-2,j-1]&&dp[i-1,j-1]!=dp[i-1,j-2])
dp[i, j] = Math.Max(dp[i, j], dp[i - 1, j - 1]+(pd[i,j]>=3?1:0));
dp[i, j] = Math.Max(dp[i, j], dp[i - 1, j]);
dp[i, j] = Math.Max(dp[i, j], dp[i, j - 1]);
}
}
Console.WriteLine(dp[n-1,m-1]);
}
}
}