- dp类题目我个人感觉最难的是初始化... 可能是我太弱了 初始化问题始终困扰我,对于区间dp 初始化最小区间即可,推出之后大区间所需要的最小区间 下面关于此题
- 对于状态: 这种两个串的基本都是dp[i][j][l][r]方程较为简单
if(a[j]==a[i])dp[i][j][l][r]|=dp[i+1][j-1][l][r];
if(a[j]==b[l])dp[i][j][l][r]|=dp[i][j-1][l+1][r];
if(b[r]==a[i])dp[i][j][l][r]|=dp[i+1][j][l][r-1];
if(b[r]==b[l])dp[i][j][l][r]|=dp[i][j][l+1][r-1];
- 区间dp套路:先枚举区间大小 (因为是从小到大这种转移顺序) 然后枚举左端点i,右端点j=i+len-1;注意范围 初始化最小的区间(因为无法被转移到,是初始值)这题易知是两个串所取总长度为1时dp=1;故if(d1+d2<=1)dp[i][j][l][r]=1;