题目链接 题意也比较好懂,就是说给你一个字符串只含有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]就是答案