关注
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]的最大值，而是中间也需要保存，每次比较
相关推荐
查看15道真题和解析 04-02 10:09
门头沟学院 Java 
用微笑面对困难：这里面问题还是很多的，我也不清楚为啥大家会感觉没啥问题。首先就是全栈开发实习9个月的内容都没有java实习生的内容多，1整个技术栈没看出太核心和难点的内容，感觉好像被拉过去打杂了，而且全栈基本上很容易被毙。里面能问的bug是在太多了比如L：继承 BaseMapper 可直接使用内置方法’。请问你的 BaseMapper 是如何扫描实体类注解如果瞬时产生 100 个上传任务，MySQL 的索引设计是否会有瓶颈？你做过分库分表或者索引优化吗？全栈的内容可以针对动态难点去搞，技能特长写在下面吧，你写了这么多技能，项目和实习体现了多少？你可以在项目里多做文章然后把这个放下去，从大致来看实习不算太水，有含金量你也要写上内容针对哨兵里面的节点变化能问出一万个问题，这个很容易就爆了。
点赞 评论 收藏
分享