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

mac可以做网站开发吗优质友情链接

mac可以做网站开发吗,优质友情链接,基于java的家纺网站设计毕业论文,代发视频赚钱app思路:LCS类dp 这道题的思考思路其实就是把以两个字符串结尾作为状态方程。 dp[i][j]的意义就是在s字符串在以s[i]结尾的字符串的情况下,所能匹配出t字符串以t[j]结尾的字符串个数。 本质上其实是一个LCS类的状态方程,只不过是意义不一样了…

思路:LCS类dp

这道题的思考思路其实就是把以两个字符串结尾作为状态方程。

dp[i][j]的意义就是在s字符串在以s[i]结尾的字符串的情况下,所能匹配出t字符串以t[j]结尾的字符串个数。

本质上其实是一个LCS类的状态方程,只不过是意义不一样了,转移方程不一样了。

那么,我们知道了状态意义之后,我们就需要知道转移方程怎么写。

首先我们需要比较每一个字符串,以s作为匹配的主体,去匹配t。当s[i]==t[j]的时候,说明这个时候结尾处我们是可以用这意味匹配的,那么我们这一位考虑和t[j]匹配了之后,就只需要考虑后面的字符串就行了,也就是dp[i-1][j-1]。但是我们还有一种情况,比如bagg,和bag这个距离,我们除了判断除了dp[i-1][j-1]这个状态之外,需要知道dp[i-1][j]的状态,因为这里我们如果不考虑s[i]的匹配了(选与不选的问题),那么上一位我们就需要考虑是不是和当前t的这一位匹不匹配。

之后,就是s[i]!=t[j]的情况,这里就简单了,因为无论如何s[i]都不能满足t[j]的匹配,我们只需要考虑上一位的匹配情况就可以了。

注意:初始化的时候我们需要额外注意,在t为空的时候,我们无论怎么匹配就只有一种情况,也就是dp[i][0]=1,因为只有一个空集能够匹配;当s为空的时候,其实就没有什么匹配情况了,本身需要匹配的字符串都没有,也就没有什么个数方案了,也就是dp[0][i]=0。

当然,当s,t都是空的时候,也就是一种方案,都是匹配空集。

还有,在递推的过程中,其实dp可能会暴int,所以需要及时在中途进行类型变化并取余。

class Solution {
public:int numDistinct(string s, string t) {vector<vector<int>>dp(s.size()+1,vector<int>(t.size()+1,0));for(int i=1;i<=s.size();i++){dp[i][0]=1;}for(int i=1;i<=t.size();i++){dp[0][i]=0;}dp[0][0]=1;for(int i=1;i<=s.size();i++){for(int j=1;j<=t.size();j++){if(s[i-1]==t[j-1]){dp[i][j]=(long)(dp[i-1][j-1]+dp[i-1][j])%1000000007;}else{dp[i][j]=(long)dp[i-1][j]%1000000007;}}}return dp[s.size()][t.size()];}
};

http://www.mnyf.cn/news/43119.html

相关文章:

  • 佛山营销型网站建设公司跨境电商平台注册开店流程
  • 某企业网站建设论文宁德市人民医院
  • 做网站的视频教程网站收录登录入口
  • 企业网站建设公司名称百度新闻官网
  • 南昌高端网站开发费用表如何seo推广
  • 一台ip做两个网站百度网盟
  • 网站建设服务那一个便宜海外网站
  • 如何利用java工具做网站seo排名优化软件有
  • 校园网站建设系统设计互动营销的案例有哪些
  • 购买域名做销售网站可以吗军事网站大全军事网
  • 一个叫mit做app的网站怎么推广一个app
  • 名词解释响应式网页设计seo jsbapp9
  • 做网站怎么和广告公司合作厦门百度竞价
  • 一个旅游网站怎么做护肤品推广软文
  • 建网站做相亲交换友情链接的意义是什么
  • 郑州营销型网站制作运营靠谱的代运营公司
  • dw网站大学生代做软文平台
  • 网站空间租用有哪些服务任何东西都能搜出来的软件
  • 微信小程序营销推广优化关键词哪家好
  • 佛山专业做企业网站新开网店自己如何推广
  • b2b电子商务模式的网站深圳网站设计制作
  • 江西省建设厅网站产品推广介绍
  • 做校园网站代码搜索率最高的关键词
  • 众创空间那个网站做的好线上推广具体应该怎么做
  • 大型网站模板提升排名
  • 网站分辨率做多大自己建个网站要多少钱
  • 湛江企业网站怎么建设想做网络推广如何去做
  • 做网站建设跑业务武汉seo培训
  • IT男为女朋友做的求婚网站口碑营销的案例及分析
  • 网易企业邮箱价格网站排名优化+o+m