题目重点：用按选中数与第一组和索引的稀疏背包 DP，保留第二组最大和；解释负数和值域未知时的状态复杂度。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练输入为两个等长整数数组，允许负数；必须恰选 k 个相同下标，k 在 [0,n]。
- k=0 的两个和都为 0，返回 0；题目未规定这个边界。
- 返回最优 r 数值，不返回下标；若要下标需存前驱。
解题路线
- 暴力枚举 C(n,k) 个下标集合，计算 min(sum1,sum2) 作为独立基线。
- DP 状态 states[c][s1] 存选 c 个位置、第一数组和为 s1 时能得到的第二数组最大和 s2。相同 c、s1 下较小 s2 永不优于较大 s2，任何未来共同选择都保持这种支配关系。
- 逐位置 (a,b) 更新，c 从大到小遍历以保证每个下标最多使用一次；从 states[c−1] 的每个 s1 产生 (s1+a,s2+b)，保留最大 s2。
- 最终扫描 states[k]，取 max min(s1,s2)。若所有 a 非负且总和范围 S 较小，可用稠密 O(nkS) 背包；题目未明确 S，故代码用稀疏字典处理负数和未知值域。
手动走一遍
arr1=[6,3,6,5,1]、arr2=[1,4,5,9,2]、k=3，选 0、2、3 得 min(17,15)=15；扫描所有状态后才能确认是否还有更优组合。两个方案若选中数和 sum1 相同，但 sum2 分别 12 和 15，保留 15 不会丢最优。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Exact sparse-sum DP for choosing identical positions from two arrays."""
def maximize_smaller_selected_sum(first: list[int], second: list[int], k: int) -> int:
if len(first) != len(second) or not 0 <= k <= len(first):
raise ValueError("equal lengths and 0 <= k <= n required")
# states[count][sum_first] = largest achievable sum_second.
states: list[dict[int, int]] = [{0: 0}] + [{} for _ in range(k)]
for seen, (left, right) in enumerate(zip(first, second)):
for count in range(min(k, seen + 1), 0, -1):
target = states[count]
for sum_first, sum_second in states[count - 1].items():
new_first = sum_first + left
new_second = sum_second + right
if new_second > target.get(new_first, float("-inf")):
target[new_first] = new_second
return max(min(sum_first, sum_second) for sum_first, sum_second in states[k].items())
复杂度
设 D_c 为某层可达的不同第一组和数量，时间约 O(Σ每位置Σc D_c)、空间 O(Σc D_c)；最坏 D_c 可指数增长，不能在题目缺 n/值域时保证多项式。若非负且总和上界 S，稠密版 O(nkS) 时间、O(kS) 空间。
易错点与追问
容易失分的边界
- 两个数组分别选择各自最好的 k 个下标，违背同选位置。
- 只最大化 sum1+sum2，不等价于最大化较小者。
- c 从小到大原地更新，导致同一位置被重复选择。
- 假设全部数非负并申请按总和大小的数组，题目未明确约束。
继续深挖
- 若 n 大且数值范围巨大，可否给近似算法或下界？
- 如何恢复实际所选下标而不破坏状态压缩？
- 目标改为最大化 min(sum1/权重1,sum2/权重2) 时状态如何变化？
