给你一个字符串 word ，你可以向其中任何位置插入 "a"、"b" 或 "c" 任意次，返回使 word 有效 需要插入的最少字母数。
如果字符串可以由 "abc" 串联多次得到，则认为该字符串有效 。
样例1
输入：word = "b"
输出：2
解释：在 "b" 之前插入 "a" ，在 "b" 之后插入 "c" 可以得到有效字符串 "abc" 。
样例二
输入：word = "aaa"
输出：6
解释：在每个 "a" 之后依次插入 "b" 和 "c" 可以得到有效字符串 "abcabcabc" 。
样例三
输入：word = "aaa"
输出：6
解释：在每个 "a" 之后依次插入 "b" 和 "c" 可以得到有效字符串 "abcabcabc" 。
分析
dp[i]:将前 i个字符（为了方便编码，下标从 1 开始）拼凑成若干个 abc 所需要的最小插入数。
初始化 dp[0]=0
转移过程：
- 若第i个字符只能单独构成"abc",则dp[i]=dp[i-1]+2
- 若第i个字符可与前面的字符共同构成"abc",则dp[i]=dp[i-1]-1
d[i] 取以上情况的最小值。在本题中，每个字符总是尽可能的与前面的字符去组合，因此情况 2优于情况 1
class Solution {
public:
int addMinimum(string word) {
int n = word.size();
int dp[n+1]; //使前n个字符构造为有效字符串所需的最小插入数
dp[0]=0;
for(int i=1;i<=n;i++){
//如果第i个字符在“abc”中是单个字符
dp[i]=dp[i-1]+2; //单独构成
if(word[i]>word[i-1]) //可与前面的字符组成有效字符串
dp[i]=dp[i-1]-1; //这种情况比起上面的情况更优
}
return dp[n];
}
};