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

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];

全部评论

相关推荐

点赞 评论 收藏
分享
能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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