Hello 2024
内容提要
本文讨论了几道算法题，包括Alice与Bob的博弈、字符串拆分成本最小化、字符串分组成本最小化以及01字典树的构建问题。每道题目提供了解题思路和代码实现，旨在帮助读者理解算法的应用与优化。
延伸解读
博弈问题的数学简化
Alice与Bob的博弈问题中，虽然规则允许每次从任一钱包取钱，但最终胜负仅取决于两个钱包金额总和的奇偶性。这是因为双方的操作会相互抵消，总操作次数固定为总和，因此先手胜负由总和模2决定。这种简化体现了博弈问题中寻找不变量或奇偶性的常见思路。
字符串拆分成本最小化的贪心策略
对于由'-'和'+'组成的字符串，拆分成本定义为每段和的绝对值乘以段长。最优策略是尽可能将和不为0的字符单独成段，因为合并它们会增加成本；而和为0的段可以合并以降低成本。最终最小成本等于整个字符串中'-'和'+'数量之差的绝对值。
分组增加问题的贪心模拟
将字符串拆分成两个子序列，每个子序列内相邻正序对（前一个数小于后一个数）的数量即为成本。贪心策略是维护两个子序列的末尾值，对于每个新元素，优先放入不会增加成本或增加成本较小的子序列。具体实现中，根据当前两个末尾值与新元素的大小关系进行决策，最终成本为累计增加数减2（因为初始两个子序列各有一个元素，不计成本）。
01字典树构建的逆向思维
给定叶子节点的值（1的数量）和顺序，判断是否存在对应的01字典树。解题思路是从最大值开始，每次寻找相邻的、值恰好小1的节点进行合并，合并后的父节点值取较小者。这个过程类似于哈夫曼编码的逆向构建，最终若只剩下一个值为0的节点，则说明可以构建。算法利用有序映射和索引列表高效实现。
Q&A
Alice与Bob的博弈问题是如何解决的？
通过计算两个钱包中钱的总和对2的取模来判断谁会没有办法操作。
字符串拆分成本最小化的目标是什么？
目标是将由'-'和'+'组成的字符串拆分成多个段，使得所有段的成本之和最小。
如何实现字符串分组成本最小化？
采用贪心算法将字符串拆分成两个子序列，计算相邻正序对的成本。
01字典树的构建问题涉及哪些关键步骤？
判断是否可以构建字典树的关键在于检查相邻节点的值是否符合条件，类似于哈夫曼编码的过程。
在字符串拆分成本最小化中，如何处理和为0的情况？
除了和等于0的情况，其他情况都不应合成一个段。
字符串分组成本最小化的成本计算方式是什么？
每个子序列内，每有一对相邻的正序对就算一个成本。
