回文子串
dp[i][j]:[i, j]范围内为回文子串
递推式
分三种情况
①:ij相等 显然是回文
②:j - i < 1 且 s[i] == s[j] 显然是回文
③:j - i > 1 且 dp[i + 1][j - 1]为true 也就是当前两端元素相同 看元素内部是否是回文 如果是 显然是ij范围内是回文
初始化必须初始化false true的话整个字符串变成回文了
遍历i的时候一定要从下到上遍历,这样才能保证下一行的数据是经过计算的。
最长回文子序列
dp[i][j]:字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
两端如果相同 那么就迭代+2
如果不同 就分别考虑一端 求最大的值
初始化 ij下标相同时初始化为1 其他初始化为0
遍历i的时候一定要从下到上遍历,这样才能保证下一行的数据是经过计算的。
标签:子串,初始化,遍历,随想录,day60,ij,dp,回文 From: https://www.cnblogs.com/mingtiao/p/18031689