小扣出去秋游，途中收集了一些紅葉和黃葉，他利用這些葉子初步整理了一份秋葉收藏集 leaves， 字串 leaves 僅包含小寫字符 r 和 y， 其中字符 r 表示一片紅葉，字符 y 表示一片黃葉，
出于美觀整齊的考慮，小扣想要將收藏集中樹葉的排列調整成「紅、黃、紅」三部分，每部分樹葉數量可以不相等，但均需大于等于 1，每次調整操作，小扣可以將一片紅葉替換成黃葉或者將一片黃葉替換成紅葉，請問小扣最少需要多少次調整操作才能將秋葉收藏集調整完畢，
示例 1：
輸入：leaves = "rrryyyrryyyrr"
輸出：2
解釋：調整兩次，將中間的兩片紅葉替換成黃葉，得到 "rrryyyyyyyyrr"
示例 2：
輸入：leaves = "ryr"
輸出：0
解釋：已符合要求，不需要額外操作
提示：
3 <= leaves.length <= 10^5
leaves 中只包含字符 'r' 和字符 'y'
解題思路：
這道題目是一個典型的動態規劃題，最復雜的部分當屬dp的構建，dp[i][j]表示在狀態i的情況下，從0到j的順序中
需要調整的最小值，按照這個思路，那么對于讀入的’r’與’y’就要分開討論，代碼如下：
class Solution {
public:
int minimumOperations(string leaves) {
int INF = 0x3f3f3f3f;
vector<vector<int>> dp(3, vector<int>(leaves.size(), INF));
//dp[0]代表第一紅,dp[1]代表第二黃,dp[2]代表第三紅
if (leaves[0] == 'r') {
dp[1][0] = 1;
dp[0][0] = 0;
//第三個紅色不可能在起始位置，所以必須初始化為無窮
}
//同理，第二個黃色不可能在起始位置，初始化INF
else dp[0][0] = 1;
for (int i = 1; i < leaves.size(); i++) {
if (leaves[i] == 'r') {
dp[0][i] = dp[0][i - 1];
//dp[1][i] = min(y->y, r->y) + 1 (y變成r次數加1) 前一個是red或者yellow都行
dp[1][i] = min(dp[0][i - 1], dp[1][i - 1]) + 1;
//dp[2][i] = min(y->r, r->r) 前一個是yellowyellow或者red都行
dp[2][i] = min(dp[1][i - 1], dp[2][i - 1]);
}
else {
dp[0][i] = 1 + dp[0][i - 1];
//dp[1][i] = min(y->y, r->y)
dp[1][i] = min(dp[0][i - 1], dp[1][i - 1]);
//dp[2][i] = min(y->r, r->r) + 1 (r變成y次數加1)
dp[2][i] = min(dp[1][i - 1], dp[2][i - 1]) + 1;
}
}
return dp[2][leaves.size() - 1];
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/152547.html
標籤：其他
上一篇：IR LEARN分析與實作