leetcode 730. 统计不同回文子序列_子序列回文数固定长度_酱酱熊的博客-程序员秘密

题目链接
思路一：动态规划（三维数组）
分析：对于每个符合题目条件的回文串，一定是a、b、c、d中的某个字符开头和结尾的。那么可以将这四个字符开头当作一个状态。
定义dp: dp[x][i][j]表示以x开头和结尾的并且字符串范围在s[i:j]中的回文子序列的个数。其中x表示abcd中的某个字符。
首先初始化。对于长度为1的字符串肯定是回文。
所以dp[x][i][i]=1，此时的x应该为s.charAt(i)。

状态转移方程：

当s[start]==x && s[end]==x，那么对于s[start+1:end-1]中的任意要给回文序列，头和尾加上x，肯定也还是一个回文，并且是一个新的回文，并且还会多出x和xx两个回文序列。所以状态转移方程是：dp[x][start][end]=2+dp[k][start+1][end-1],其中k为a、b、c、d。
当s[start]==x && s[end] != x，转移方程为：dp[x][start][end] = dp[x][start][end-1]
当s[start] != x && s[end]==x，转移方程为：dp[x][start][end] = dp[x][start+1][end]
当s[start] != x && s[end] != x，转移方程为：dp[x][start][end] = dp[x][start+1][end-1]

最后的答案应该为以a、b、c、d四个字符结尾的范围是[0][len-1]的dp相加。
代码：

class Solution {
    
    public int countPalindromicSubsequences(String s) {
    
        int len = s.length();
        int MOD = 1000_000_000 + 7;
        if(len==1){
    
            return 1;
        }
        int[][][] dp = new int[4][len][len]; //dp[x][i][j]表示 以x开头和结尾 的并且字符串范围在s[i:j]中的回文子序列的个数

        //初始化dp  len=1
        for(int i=0; i<len; i++){
    
            dp[s.charAt(i)-'a'][i][i] = 1;
        }

        //长度从2开始遍历到len
        for(int l=2; l<=len; l++){
    
            for(int start = 0; start+l-1<len; start++){
    
                int end = start+l-1;
                //遍历四种字符
                for(int j=0; j<4; j++){
    
                    char c = (char)('a'+j);
                    if(s.charAt(start)==c && c ==s.charAt(end)){
    
                        dp[j][start][end] =
                                (2+//2 表示 c 和cc两个回文字符串
                                (dp[0][start+1][end-1]+ dp[1][start+1][end-1])%MOD
                                        +
                                (dp[2][start+1][end-1]+ dp[3][start+1][end-1])%MOD
                                )%MOD;
                    }else if(s.charAt(start)==c){
    
                        dp[j][start][end] = dp[j][start][end-1];
                    }else if(s.charAt(end)==c){
    
                        dp[j][start][end] = dp[j][start+1][end];
                    }else{
    
                        //s.charAt(start)!=c && c !=s.charAt(end)
                        dp[j][start][end] = dp[j][start+1][end-1];
                    }
                }
            }
        }

        int res = 0;
        for(int i=0; i<4; i++){
    
            res = (res+dp[i][0][len-1])%MOD;
        }
        return res;
    }
}

本文链接：https://blog.csdn.net/weixin_42496727/article/details/125232168

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

matlab循环平稳工具箱,[MATLAB工具箱] 循环调用fmincon工具箱问题_南洋野人的博客-程序员秘密

循环调用fmincon工具箱问题请大侠给看看我的程序出的问题：%目标函数m文件：function f=fun3(x,r)f=8/(4.4^2)*x(2)*(x(1)-1)*2/3.14*acos(exp((-1.5)*(22-r)/22/sin(atan((1-x(1))/(0.2*r)/(1+x(2))))))*((0.2*r)^3);*************************...

关于jdk1.8中ConcurrentHashMap的方方面面_1.8 concurrenthashmap_亦游的博客-程序员秘密

前言Java JDK升级到1.8后有些集合类的实现有了变化，其中ConcurrentHashMap就有进行结构上的大调整。jdk1.6、1.7实现的共同点主要是通过采用分段锁Segment减少热点域来提高并发效率，1.8版本的实现有哪些变化呢？重要概念在正式研究前，我们需要先知道几个重要参数，提前说明其值所代表的意义以便更好的讲解源码实现。table所有数据都存在tab...

宝塔安装supervisord，添加thinkphp queue队列守护进程，程序不处理队列信息_supervisord queue_qq_27006679的博客-程序员秘密

错误描述在supervisord中开启了队列守护进程，但是发送数据后在redis中显示错误信息。错误提示抱歉，出错了：<br> Traceback (most recent call last):<br> File "class/flask_sockets.py", line 30, in __call__<br> handler, values = adapter.match()<br> File "/www/server/panel/...

上拉加载下拉刷新了解下_前端大全的博客-程序员秘密

（点击上方公众号，可快速关注）作者：信心 https://juejin.im/post/5b9091e7e51d450e70423161老样子，我们先，哦不，今天我们直接...

[Android] 微信apk.1安装器，200k可隐藏解决微信传apk自动改名apk.1f无法安装问题_微信传的apk_ganggang4321的博客-程序员秘密

软件名：微信apk.1安装器大小：250k版本：1.9微信最无用的设计之一：apk自动变成apk.1，想要安装，必须下载qq浏览器才行。下载地址:https://n802.com/f/349707-483747492-f50c5a（访问密码：5036）http://www.yimuhe.com/file-4856172.htmlhttps://www.90pan.com/b2350119密码：6tsk转载请注明出处：https://blog.bitefu.net...

mkimage使用详解（转载）_weixin_30725467的博客-程序员秘密

uboot源代码的tools/目录下有mkimage工具，这个工具可以用来制作不压缩或者压缩的多种可启动映象文件。mkimage在制作映象文件的时候，是在原来的可执行映象文件的前面加上一个0x40字节的头，记录参数所指定的信息，这样uboot才能识别这个映象是针对哪个CPU体系结构的，哪个OS的，哪种类型，加载内存中的哪个位置，入口点在内存的那个位置以及映象名是什么[email protected]:/...