LCP 19 DP

题意

传送门 LCP 19

题解

$dp[i][j]$ 代表字符串分别为连续的 ′ r ′ ( j = 0 ) 'r'(j=0) ′r′(j=0)，连续的 ′ r y ′ ( j = 1 ) 'ry'(j=1) ′ry′(j=1)，以及连续的 ′ r y r ′ ( j = 2 ) 'ryr'(j=2) ′ryr′(j=2) 所需的最小调整次数
{ d p [ i ] [ 0 ] = d p [ i − 1 ] [ 0 ] + ( s t r [ i ] = = ′ r ′ ? 0 : 1 ) d p [ i ] [ 1 ] = m i n ( d p [ i − 1 ] [ 1 ] , d p [ i − 1 ] [ 0 ] ) + ( s t r [ i ] = = ′ y ′ ? 0 : 1 ) d p [ i ] [ 2 ] = m i n ( d p [ i − 1 ] [ 2 ] , d p [ i − 1 ] [ 1 ] ) + ( s t r [ i ] = = ′ r ′ ? 0 : 1 ) \begin{cases}dp[i][0] = dp[i-1][0] + (str[i]=='r' ? 0 : 1) \\dp[i][1] = min(dp[i-1][1], dp[i-1][0]) + (str[i]=='y' ?0:1) \\ dp[i][2] = min(dp[i-1][2], dp[i-1][1])+ (str[i]== 'r'?0:1)\end{cases} ⎩⎪⎨⎪⎧​dp[i][0]=dp[i−1][0]+(str[i]==′r′?0:1)dp[i][1]=min(dp[i−1][1],dp[i−1][0])+(str[i]==′y′?0:1)dp[i][2]=min(dp[i−1][2],dp[i−1][1])+(str[i]==′r′?0:1)​

class Solution {
#define maxn 100005
#define inf 0x3f3f3f3f
public:int dp[maxn][3];int minimumOperations(string leaves) {memset(dp, 0, sizeof(dp));int n = leaves.size();dp[0][0] = leaves[0]=='r' ? 0 : 1, dp[0][1] = dp[0][2] = inf;for(int i=1;i<n;i++){char c = leaves[i];dp[i][0] = dp[i-1][0] + (c=='r' ? 0 : 1);dp[i][1] = min(dp[i-1][1], dp[i-1][0]) + (c=='y' ?0:1);dp[i][2] = min(dp[i-1][2], dp[i-1][1])+ (c == 'r'?0:1);}return dp[n-1][2];}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！