贪心:在每一步,若能跳 2 就优先跳 2;否则跳 1。 理由:两步跳比一步跳更“划算”,且跳 2 不会阻断可达性(题意保证存在解)。若某处能跳 2 却选择跳 1,只会增加一次额外跳跃而不带来任何好处,因此始终优先跳 2 是最优。
O(n)
,每个位置最多检查一次。O(1)
,仅常数额外变量。有一个新的手机游戏,里面有很多不同的云其中一些云是雷云,其他都是积云。
玩家可以跳上任何一个编号与当前云加 1 或 2 相等的积云。而玩家必须避开雷云。请确定从起始位置跳到最后一朵云需要的最小跳数。
假设玩家总是可以赢得游戏。
对于每个游戏,你会得到一个数组,其中编号为 0 的云表示是积云,编号为 1 的云表示需要雷云。