本文介绍一种基于优先队列（最小堆）的算法，用于在允许重复选取、且必须按数组顺序连续选取（即不可跳过中间元素）的前提下，找出所有可能组合中不小于给定 limit 的最小和与最大和，避免递归爆栈与动态规划状态设计错误。
本文介绍一种基于优先队列（最小堆）的算法，用于在允许重复选取、且必须按数组顺序连续选取（即不可跳过中间元素）的前提下，找出所有可能组合中**不小于给定 limit 的最小和**与**最大和**，避免递归爆栈与动态规划状态设计错误。
该问题本质是带约束的有界整数线性组合搜索：给定升序整数数组 arr 和目标阈值 limit，需构造一个非空序列，满足：
- 所有元素均来自 arr，可重复使用；
- 选取必须遵循数组索引顺序：若当前选了 arr[i]，下一步只能选 arr[i]（重复）或 arr[i+1]（前进），禁止跳过 arr[i+1] 直接取 arr[i+2]；
- 累加和首次 ≥ limit 时停止（即“贪心终止”条件）；
- 在所有合法终止和中，求最小值（下界达标和）与最大值（上界达标和）。
⚠️ 注意：原题中“不能跳过元素”的真实含义并非“必须包含所有元素”，而是路径必须沿数组索引单调不减地延伸——即状态转移仅允许 (i) → (i)（复用当前）或 (i) → (i+1)（推进到下一个），这正是本解法建模的核心。
✅ 正确解法：Dijkstra 风格优先队列搜索
我们把每个搜索状态定义为 (current_sum, next_index)，表示当前累加和为 current_sum，下一步可从 arr[next_index] 开始选取（含复用）。为高效获取最小达标和，使用最小堆按 current_sum 排序；同时全程记录已探索过的 (sum, idx) 状态，避免重复入队。
import heapq
from typing import Tuple, Optional, List, Any
def min_max_limit_sum(arr: List[int], limit: int) -> Tuple[int, int]:
"""
返回 (min_sum >= limit, max_sum >= limit)
约束：选取必须按 arr 索引顺序进行（可重复当前，或推进至下一个，不可跳跃）
"""
if not arr or limit <= 0:
raise ValueError("Invalid input")
# 状态：(current_sum, next_index, is_terminated)
# 使用最小堆保证先扩展小和，快速找到 min_sum
heap = [(0, 0, False)] # (sum, next_idx, terminated)
visited = set()
best_min = float('inf')
best_max = float('-inf')
while heap:
s, i, terminated = heapq.heappop(heap)
# 去重：(sum, next_idx) 相同的状态无需重复处理
state = (s, i)
if state in visited:
continue
visited.add(state)
# 若已终止，更新极值
if terminated:
if s >= limit:
best_min = min(best_min, s)
best_max = max(best_max, s)
continue
# 尚未终止：尝试两种操作
# 1. 复用 arr[i]（若 i 有效）
if i < len(arr):
new_s = s + arr[i]
# 若已达限，立即终止并记录
if new_s >= limit:
heapq.heappush(heap, (new_s, i, True))
else:
# 否则继续扩展：仍可复用 arr[i] 或推进到 arr[i+1]
heapq.heappush(heap, (new_s, i, False)) # 复用当前
if i + 1 < len(arr):
heapq.heappush(heap, (new_s, i + 1, False)) # 推进到下一个
# 2. 初始推进（从 arr[0] 开始，也可直接选 arr[1]？但题目要求“不能跳过”，故必须从 0 起步）
# 注：本实现隐含起点为 arr[0]，符合题意“有序数组”与示例逻辑
if best_min == float('inf') or best_max == float('-inf'):
raise ValueError(f"No valid combination reaches limit {limit}")
return best_min, best_max
# ✅ 验证示例
print(min_max_limit_sum([100, 200, 300, 1000], 1000)) # → (1000, 1900)
print(min_max_limit_sum([3, 10, 15], 1000)) # → (1000, 1014)? 关键设计解析
- 状态去重 (sum, idx)：防止因不同路径到达相同 (sum, idx) 而重复计算，显著降低时间复杂度；
- 双分支扩展：每个未终止状态生成两个新状态——复用当前元素（保持 i 不变）、推进到下一元素（i+1），严格满足“不可跳过”约束；
- 提前终止判断：一旦 s + arr[i] >= limit，立即压入终止状态，确保所有达标和都被捕获；
- 极值同步更新：在终止状态出堆时即时更新 best_min / best_max，无需额外遍历。
⚠️ 原实现缺陷复盘
- 递归方法：无状态剪枝，易因重复路径爆炸导致错误结果（如加入 10000 后误将 10000 作为首项直接达标，忽略更优的 100+200+300+1000=1900 组合）；
- 动态规划方法：状态维度设计不当（table[i][j] 含义模糊），未建模“顺序依赖”与“终止时机”，导致 min_cap / max_cap 更新逻辑失效。
✅ 总结
本方案以图搜索视角建模，将组合生成过程视为有向图上的路径遍历，利用最小堆保障最优子结构优先扩展，兼具正确性、鲁棒性与可读性。适用于 limit 较大但 arr 规模适中（≤ 20）的场景；若 limit 极大（如 1e9），可进一步结合数学优化（如硬币问题中的 Frobenius 数边界剪枝），但本题约束下堆搜索已足够高效。
