PAT A1030 动态规划

栏目: 编程工具 · 发布时间: 5年前

内容简介:这道题是动态规划几大问题的其中一种,为最长回文子串问题;动态规划个人来说,觉得最重要的就是建立状态转移方程。对于方程变量,我认为最重要的是有几个构成的关键变量;

PAT A1030 动态规划

这道题是动态规划几大问题的其中一种,为最长回文子串问题;

动态规划个人来说,觉得最重要的就是建立状态转移方程。对于方程变量,我认为最重要的是有几个构成的关键变量;

对于这道题,我们着手于i~j个字符,所以关注点在于i和j,所以我们建立一个二维矩阵来保存动态规划途中的计算值。对于dpi,其值为1时,意为i-j的字串是回文子串,为其他值则不是;

对于状态转移方程,我们可以这样想:对于一个回文子串,其子串也是回文子串,所以就有方程转移的定律:

dpi=dpi+1

接下来就是如何遍历;

对于遍历,我们一定要保证从边界开始,并且现有计算状态必须建立在已有建立状态之上。由于转换方程的特殊性,i,j两个坐标都像两边扩散,所以我们可以根据L,也就是子串的长度来进行计算;

先将单个字符相应的值置为1,然后L=2.....至L=n;在途中记录子串的长度;

代码如下所示:

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<cstring>
#include<string>
using namespace std;
const int maxn=1010;
string data;
int matrix[maxn][maxn];
int main(){
    getline(cin,data);
    int len=data.size();
    for(int i=0;i<len;i++){
        matrix[i][i]=1;
    }
    int ans=1;
    for(int i=1;i<len;i++){
        if(data[i-1]==data[i]){
            matrix[i-1][i]=1;
            ans=2;
        }
    }
    for(int L=3;L<=len;L++){
        for(int i=0;i+L-1<len;i++){
            int j=i+L-1;
            if(data[i]==data[j]&&matrix[i+1][j-1]==1){
                matrix[i][j]=1;
                ans=L;
            }
        }
    }
    printf("%d\n",ans);
    system("pause");
    return 0;
}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

写给大家看的设计书(第4版)

写给大家看的设计书(第4版)

Robin Williams / 苏金国、李盼 / 人民邮电出版社 / 2016-1 / 59.00元

畅销设计入门书最新版,让每个人都能成为设计师 在这个创意无处不在的时代,越来越多的人成为设计师。简历、论文、PPT、个人主页、博客、活动海报、给客人的邮件、名片……,处处都在考验你的设计能力。 美术功课不好?没有艺术细胞?毫无设计经验? 没关系!在设计大师RobinWilliams看来,设计其实很简单。在这部畅销全球多年、影响了一代设计师的经典著作中,RobinWilliams将......一起来看看 《写给大家看的设计书(第4版)》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

在线进制转换器
在线进制转换器

各进制数互转换器

MD5 加密
MD5 加密

MD5 加密工具