贪心算法：
1.从字符串头开始扫描；设res为计算结果；
2.想象有一个堆栈，遇到“{”就放到堆栈里，遇到“}”就把堆栈POP出一个“{”来匹配；
3.如果遇到“}”的时候堆栈为空，就把这个“}”替换为“{”放到堆栈里，res加1；
4.如果字符串扫描完了，堆栈里还有X个“{”（X肯定是偶数），就把栈顶的X/2个“{”替换为“}”与剩下的X/2个“{”匹配，res加上X/2；
5.实际代码不需要堆栈，只需一个计数器


证明：
1.每次堆栈为空的时候遇到“}”，说明已扫描那部分字符串的“}”比“{”多1个，要实现完全匹配，至少要把1个“}”替换为“{”；
2.最后堆栈里剩下的X个“{”(只有最底下那个可能是“}”置换来的），要实现完全匹配，至少要把X/2个“{”替换为“}”
3.于是计算出了最小替换个数的一个下限，这个下限正好是上面算法得到的结果

• 代码 (759) cavatina2016 2020-08-01 01:17:44
• 算法与证明(revised) (833) cavatina2016 2020-08-01 15:43:00