LeetCode 秋叶收藏集

    科技2022-07-20  104

    题目描述

    题目链接 题意也比较好懂,就是说给你一个字符串只含有r和y这两种字符,每次操作可以翻转一个字符,把r变成y或者把y变成r。问把整个字符串翻转成[r…y…r]的形式至少需要多少次?

    题目分析

    其实也比较好思考。考虑dp[i][j]表示[0,i]的字符串全部处理好了并且第i个字符是状态是j的情况,其实j只有三种选择(r1,y,r2)这个r1和r2不是一种状态,r1代表y还没有出现,r2代表y已经出现过了。那么转移其实也显而易见了: (1)dp[i][0]的转移 dp[i][0]的含义就是前i个都是r,因为这时y没有出现过,那么只需要考虑第i位是不是r就行了,不是就需要操作加1 dp[i][0]=dp[i-1][0]+(leaves[i]==y) (2)dp[i][1]的转移 其实这个转移也很好推,dp[i][1]代表当前出现的是y这一段,那么他就只有两种可能,前边出现过或者前边没有出现过,前边出现过就是dp[i-1][1],没有出现过就是dp[i-1][0].这两个取个最小值即可。 dp[i][1]=min(dp[i-1][1],dp[i-1][0])+(leaves[i]==r) (3)dp[i][2]的转移 考虑此时的状态就是出现过了ry,到第三个r了。那么他也只有两种转移,要么前边已经出现过r,要么从这当前开始出现r,如果是从当前出现r,说明前边肯定是y。所以这里的转移就是: dp[i][2]=min(dp[i-1[2],dp[i-1][1])+leaves[i]==y 这里的坑就是不能从dp[i][0]直接转移过来。 然后dp[leaves.size()-1][2]就是答案

    代码

    class Solution { public: int minimumOperations(string leaves) { if (leaves.size() == 0)return 0; const int maxn = 1e5 + 10; int dp[maxn][3]; dp[0][0] = (leaves[0] == 'r' ? 0 : 1); dp[0][1]= dp[0][2] = INT_MAX; dp[1][2] = INT_MAX; for (int i = 1; i < leaves.size(); i++) { dp[i][0] = dp[i - 1][0] + (leaves[i] == 'y'); dp[i][1] = min(dp[i - 1][0],dp[i - 1][1]) + (leaves[i] == 'r'); if (i >= 2) { dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + (leaves[i] == 'y'); } } return dp[leaves.size() - 1][2]; } };
    Processed: 0.013, SQL: 8