LC 45

Jump Game II

Medium · LC 1–100

arraydynamic-programminggreedy
Free
打开 LeetCode 题目

候选解法路线

Primary

交换论证 / 局部最优排序

Free

Invariant: 贪心前缀无局部逆序，而且至少存在一个全局最优解与该前缀完全一致。

candidate confidence: 0.666 · metadata_only

打开候选模板
Alternate 1

线性 DP / 一维状态递推

Free

Invariant: 计算完 i 后，所有不超过 i 的状态都等于其定义下的真实最优值/计数；任何未来转移只读取这些已完成状态。

candidate confidence: 0.470 · metadata_only

打开候选模板

如何使用本页

先读原题与 constraints，再逐一验证 Recognition signals、invariant 与 complexity；candidate score 不能证明正确性。