LeetCode dp

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

dp解法

class Solution {
public:
    int minCost(string s, vector<int>& cost) {
        int n = s.size();
        vector<vector<int>> f(n + 1, vector<int>(26));
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 26; ++j) {
                f[i][j] = f[i - 1][j] + cost[i - 1];
            }
            int t = s[i - 1] - 'a';
            for (int j = 0; j < 26; ++j) {
                if (j != t) {
                    f[i][t] = min(f[i][t], f[i - 1][j]);
                }
            }
        }
        return *min_element(f[n].begin(), f[n].end());
    }
};

非dp解法

（我的）

class Solution {
public:
    int minCost(string s, vector<int> &cost) {
        int res = 0;
        for (int i = 1; i < s.size(); i++) {
            int curcost = cost[i - 1];
            int curmax = cost[i - 1];
            while (i<s.size() && s[i - 1] == s[i]) {
                curcost += cost[i];
                curmax = max(curmax, cost[i]);
                i++;
            }
            res += curcost - curmax;
        }
        return res;
    }
};

（别人的）

class Solution {
public:
    int minCost(string s, vector<int>& cost) {
        int n = s.size();
        int sum = 0;
        for(int i = 0;i<n-1;i++)
        {
            if(s[i] == s[i+1])
            {
                sum+= min(cost[i],cost[i+1]); 
                if(cost[i]>cost[i+1])swap(cost[i],cost[i+1]);
            }
        }
        return sum;
    }
};