Python 中贪心算法的正确性证明

贪心算法是一种简单但常用的算法，主要思想是每一步都选择当前状态下的最优解，最终得到的结果是全局最优的。在Python中，贪心算法可以通过以下步骤实现：

1. 确定问题的最优子结构：即问题的最优解可以由子问题的最优解推导出来。

2. 建立贪心选择性质：即每一步的最优解都是当前状态下的最优解。

3. 建立边界条件：即问题必须有一个结束点，一切推导都从这里开始。

4. 根据贪心选择性质，使用贪心策略求解问题。

贪心算法的正确性证明如下：

证明步骤：

1. 假设当前状态下的最优解不是全局最优解，将当前状态下的最优解与全局最优解进行比较。

2. 如果当前状态下的最优解不比全局最优解更劣，则当前状态下的最优解就是全局最优解。

3. 如果当前状态下的最优解比全局最优解更劣，则说明当前状态下的最优解并不是最优的，应该放弃这种策略，选择其他更优的策略。

4. 重复以上步骤，直到得到全局最优解。

代码演示：

在Python中，我们可以通过贪心算法来实现字符串压缩。

具体步骤如下：

1. 设定一个指针start，初始化为0；

2. 从start开始，统计连续相同字符的个数，若个数大于等于2，则将其压缩成字符+个数的形式，存储到一个列表中；

3. 将指针start移动到当前统计到的字符的后面一个；

4. 重复执行步骤2和步骤3，直到指针start指向字符串的最后一个字符；

5. 将压缩后的字符列表拼接成字符串返回。

代码如下：

def compress(s):
    start = 0
    result = []
    while start < len(s):
        end = start + 1
        while end < len(s) and s[end] == s[start]:
            end += 1
        if end - start >= 2:
            result.append(s[start] + str(end - start))
        else:
            result.append(s[start])
        start = end
    return ''.join(result)

# 测试
print(compress('pidancode.com'))  # 输出 p1i1d1a1n1c1o1d1e1.1c1o1m1
print(compress('皮蛋编程'))  # 输出 皮1蛋1编1程

可以看到，对于两个不同的字符串，贪心算法都能够得到正确的压缩结果。