1578. 避免重复字母的最小删除成本

　　方法一：动态规划

class Solution {
public:
    int minCost(string s, vector<int>& cost) {
        int n = s.size(),INF = 1e9;
        vector<vector<int>> f(n,vector<int>(27,INF)); // f[i][j] 删除前i个字符，最后一个为j的最小代价，j为26表示全删完没最后一个
        f[0][s[0]-'a'] = 0, f[0][26] = cost[0]; 
        for(int i = 1; i < n; i++) {
            for(int j = 0;  j < 27; j++) f[i][j] = f[i-1][j] + cost[i]; // 删去第i个
            int j = s[i] - 'a';
            for(int k = 0; k < 27; k++) {  // 保留第i个
                if(k != j) {
                    f[i][j] = min(f[i][j],f[i-1][k]);
                }
            }
        }
        int res = INF;
        for(int i = 0; i < 27; i++) res = min(res,f[n-1][i]);
        return res;
    }
};

　　方法二：贪心

class Solution {
    public int minCost(String s, int[] cost) {
        int n = s.length();
        int res = 0;
        for(int i = 0; i < n - 1; i++) {
            int sum = cost[i], max = cost[i];
            while(i < n - 1 && s.charAt(i) == s.charAt(i+1)) {
                sum += cost[i+1];
                max = Math.max(max,cost[i+1]);
                i++;
            }
            res += sum - max;
        }
        return res;
    }
}