关注
516 最长回文子序列
暴力也很复杂，因为不连续，有无数种组合
所以这种只能动态规划
状态转移方程就是
如果首位字符相等
dp[i][j] = dp[i+1][j-1] + 2
如果不相等，max（dp[i][j-1], dp[i+1][j]）
那我们可以看到，每次都是与j-1以及i+1相关，实际上这就是复用了之前的状态
那么i应该是倒序，j应该是正序
for i : n-1 --- 0 //倒序遍历
dp[i][i] = 1 //初始条件应该是一个字符为1
for j : i+1 --- n-1
按照上面的状态转移即可
最后就是dp[0][n-1] 就是最大的长度
这种一看就是有递推关系的
笔试题基本必出动态规划
所以这种只能动态规划
状态转移方程就是
如果首位字符相等
dp[i][j] = dp[i+1][j-1] + 2
如果不相等，max（dp[i][j-1], dp[i+1][j]）
那我们可以看到，每次都是与j-1以及i+1相关，实际上这就是复用了之前的状态
那么i应该是倒序，j应该是正序
for i : n-1 --- 0 //倒序遍历
dp[i][i] = 1 //初始条件应该是一个字符为1
for j : i+1 --- n-1
按照上面的状态转移即可
最后就是dp[0][n-1] 就是最大的长度
这种一看就是有递推关系的
笔试题基本必出动态规划
全部评论
注意当i-i+1 字符相等的时候， dp[i+1][i] 默认就是0此时dp就为2
1682. 最长回文子序列 II
各种动态规划的变体都是变成三维，比如这里就是必须是偶数，以及除了中间相同其他必须不连续相同；
第一种就是初始条件就是不仅i<j dp为0，i=j也为0
第二种就是 第三维[k]代表26个字母结尾的，每次遍历26个字母，该字母k+'a'下再次遍历26个字母结尾的之前的dp，如果相等则continue这意味这k-k的dp为0，这样子最后并不是dp[0][n-1][0-25]的最大值，而是中间也需要保存，每次比较
相关推荐
百度泡池子136人在聊
投递TP-LINK等公司10个岗位 点赞 评论 收藏
分享
