当前位置: 首页 > news >正文

网站响应式好吗东莞做一个企业网站

网站响应式好吗,东莞做一个企业网站,wordpress显示新闻,企业网站的技术维护内容主要包括给你一个字符串 s ,返回 s 中不同的非空回文子序列个数 。由于答案可能很大,请返回对 109 7 取余 的结果。 字符串的子序列可以经由字符串删除 0 个或多个字符获得。 如果一个序列与它反转后的序列一致,那么它是回文序列。 如果存在某个 …

给你一个字符串 s ,返回 s 中不同的非空回文子序列个数 。由于答案可能很大,请返回对 109 + 7 取余 的结果。

字符串的子序列可以经由字符串删除 0 个或多个字符获得。

如果一个序列与它反转后的序列一致,那么它是回文序列。

如果存在某个 i , 满足 ai != bi ,则两个序列 a1, a2, … 和 b1, b2, … 不同。

示例 1:
输入:s = ‘bccb’
输出:6
解释:6 个不同的非空回文子字符序列分别为:‘b’, ‘c’, ‘bb’, ‘cc’, ‘bcb’, ‘bccb’。
注意:‘bcb’ 虽然出现两次但仅计数一次。

示例 2:
输入:s = ‘abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba’
输出:104860361
解释:共有 3104860382 个不同的非空回文子序列,104860361 是对 109 + 7 取余后的值。

提示:
1 <= s.length <= 1000
s[i] 仅包含 ‘a’, ‘b’, ‘c’ 或 ‘d’

三维DP

class Solution {
public:int countPalindromicSubsequences(string s) {int MOD = 1e9 + 7;int n = s.size();vector<vector<vector<int>>> dp(4, vector<vector<int>>(n, vector<int>(n, 0)));for(int i = 0; i < n; i++){dp[s[i] - 'a'][i][i] = 1; }for(int len = 2; len <= n; len++){for(int i = 0, j = len - 1; j < n; i++, j++){for(char c = 'a'; c <= 'd'; c++){char k = c - 'a';if(s[i] == c && s[j] == c){dp[k][i][j] = (2LL + dp[0][i+1][j-1] + dp[1][i+1][j-1] + dp[2][i+1][j-1] + dp[3][i+1][j-1]) % MOD;}else if(s[i] == c){dp[k][i][j] = dp[k][i][j-1];}else if(s[j] == c){dp[k][i][j] = dp[k][i+1][j];}else{dp[k][i][j] = dp[k][i+1][j-1];}}}}int res = 0;for(int k = 0; k < 4; k++){res = (res + dp[k][0][n-1]) % MOD;}return res;}
};

我们定义一个三维数组dp[k][i][j]来表示在i到j范围内并且以k开头的回文子序列的总数。我们在状态转移过程中,可以先不断遍历i和j之间的范围len,那么我们接下来继续遍历i的时候,j实际上也会知道,最后在最里层循环中遍历k是多少。

当s[I] = s[j]的时候,那么i+1到j-1中的回文子序列加上两边的x都是以x为开头的回文子序列,并且字符c可以构成c或者cc两个回文子序列,所以有状态转移方程dp[k][i][j] = (2LL + dp[0][i+1][j-1] + dp[1][i+1][j-1] + dp[2][i+1][j-1] + dp[3][i+1][j-1]) % MOD;

首尾字符中只有 s[i] 是我们感兴趣的字符 c。
因此,当前子串 s[i…j] 中以 c 为边界的回文子序列,与子串 s[i…j-1] 中以 c 为边界的回文子序列是相同的,因为 s[j] 不会对结果产生影响。

接下来的几种情况同理。

最后我们定义一个变量res来记录以不同字符开头的长度为n的字符串的回文子序列总数。

http://www.ritt.cn/news/22011.html

相关文章:

  • 有源码如何搭建网站最佳搜索引擎磁力
  • wordpress静态404郑州seo哪家好
  • 百度如何验证网站seo 公司
  • wordpress 注册 地址seo入门教程视频
  • 邯郸做网站熊掌号网站里的友情链接
  • 公众号文章怎么制作seo搜索优化技术
  • 哈尔滨市哪里做淘宝网站社交媒体营销案例
  • icp备案域名网站备案信息域名停靠
  • 外贸建站哪家营销渠道
  • 网站的建设模式是指什么时候开始重庆网络推广公司
  • 网站建设团队介绍seo怎么做排名
  • 建网站手机百度优化师
  • 哪个网站做正品女装微信推广平台哪里找
  • 确定网站建设目标网站优化公司认准乐云seo
  • 做旅游网站的数据怎么来综合搜索引擎
  • 设计logo网站哪个好国家最新新闻
  • php企业网站开发pdf免费企业网站模板源码
  • 网站运营推广选择乐云seo百度知道网址
  • 怎样选择网站的关键词百度云网页版入口
  • 教育部专业申报建设 网站站长工具介绍
  • 一站式网站建设费用策划公司排行榜
  • 兰州做网站哪个平台好百度推广公司哪家比较靠谱
  • 公司网站建设介绍网站流量排行
  • 珠海网站制作系统百度搜索软件
  • wordpress页码seo入门培训
  • 都匀网站建设公司长沙seo排名优化公司
  • 杭州小程序网站开发公司今日郑州头条最新新闻
  • 网站设计风格怎么写西安网络推广公司大全
  • 郑州网站制作公司朔州网站seo
  • 黑龙江建设网安全员考试报名网站推广与优化平台