动态规划,遍历顺序问题(最长回文子序列)

dp[i][j]:str[i , j]的最长回文子序列长度

1、str[i]==str[j]:dp[i][j] = dp[i+1][j-1] + 2;

2、str[i]!=str[j]:dp[i][j] = max(dp[i+1][j] , dp[i][j-1] )

由于dp[i][j]依赖于dp[i+1][j-1]、dp[i+1][j]、dp[i][j-1],所以i要先遍历i较大的,即i从大到小遍历

根据dp定义,j>=i,注意初始化dp[i][i]=1

string str;

for(int i=0;i<str.size();i++){

        dp[i][i]=1;

    }

    for(int i=str.size()-1;i>=0;i--){

        for(int j=i+1;j<str.size();j++){

            if(str[i]==str[j]) dp[i][j]=dp[i+1][j-1]+2;

            else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);

        }

    }

    cout<<dp[0][str.size()-1];

全部评论

相关推荐

鬼迹人途:你去投一投尚游游戏,服务器一面,第一个图算法,做完了给你一个策略题,你给出方案他就提出低概率问题,答不上当场给你挂
点赞 评论 收藏
分享
lllllkin:感觉可以精简到一页简历,有些排版感觉不是必须的。 时间线越早的,你自己越熟悉的放前面。描述可以更精简些,一些问题解决感觉可以不用写具体技术栈,卖个关子,等面试官问。
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务