【每日一题】Problem 180C. Letter

原题

解决思路

每一个字符以前一个字符为基准，来判断自己是 upper 还是 lower，从而找到最少的解

1. 最开始的解决思路是，用回溯的方式来解决，即使划分区块该方法也十分耗时，因为每个字符都有两种情况，因此时间复杂度为 \(O(2^n)\)
2. 将 \(1\) 的方式修改下，分别用 \(num[i][0], num[i][1]\)来记录第 \(i\) 个字符 upper 或 lower 所需的最少次数，然后取其中最小解即所需结果
   • 当前字符为小写时
     • 如果保持不变，则前缀大写小写都可以，因此 \(num[i][0] = min(num[i-1][0], nums[i-1][1])\)
     • 如果想要大写，则前缀也必须是大写，因此 \(num[i][1] = num[i-1][1] + 1\)
   • 当前字符为大写时
     • 如果保持不变，则前缀必须是大写，因此 \(num[i][1] = num[i-1][1]\)
     • 如果想要小写，则前缀大写小写都可以，因此 \(nums[i][0] = min(num[i-1][0], num[i-1][1]) + 1\)
   • 综上，我们得到了递推公式，此时每个字符只需遍历一次，时间复杂度为 \(O(n)\)

方法 \(2\) 代码如下：

#include <bits/stdc++.h>

int main() {
    std::string s; std::cin >> s;
    std::vector<std::vector<int>> vec(s.size() + 1, std::vector<int>(2, 0));
    for (int i = 0; i < s.size(); ++i) {
        if (islower(s[i])) {
            vec[i + 1][0] = std::min(vec[i][0], vec[i][1]);
            vec[i + 1][1] = vec[i][1] + 1;
        } else {
            vec[i + 1][0] = std::min(vec[i][0], vec[i][1]) + 1;
            vec[i + 1][1] = vec[i][1];
        }
    }

    std::cout << std::min(vec[s.size()][0], vec[s.size()][1]) << std::endl;
    return 0;
}

// PRuvetSTAaYAA
// PRutSTAaYAA
// PRuvetSaYAA
// PRuvetSTAaaY
// PRuSTAaaA