精力充沛的跳蛙 - 困难的动态 Programming/Greedy 问题
Jumping Frog with Energy - Difficult Dynamic Programming/Greedy Problem
给定一组 n 块石头，它们以相同的距离排成一排。石头编号从 0 到 n-1。位于石号 0 的青蛙必须到达石号 n-1。
跳跃是从石头 i 到石头 j ( i<j ) 的移动。这样的跳转长度等于 j-i。青蛙的最大跳跃长度取决于它的能量水平（不能低于 0）。长度 j-i 的跳跃会消耗青蛙 j-i 的能量。例如，初始能量为 3，石头上的青蛙 0 最多可以跳到石头 3。
有些石头上可能有虫子，给青蛙补充能量。如果青蛙跳到上面有虫子的石头上，它必须吃虫子。列表 T[0...n-1] 包含相应石头上的蠕虫的能量值。如果石头上没有虫子，这个相当于0值。
青蛙开局0能量，但保证0号石上有虫。
给定一个列表 T，任务是 return 青蛙在到达石头 n-1 之前所到过的石头的索引列表。但是，这必须是最短的列表。在某些情况下，可能有不止一种解决方案，以接受者为准。保证青蛙总能到达石头n-1.
示例编号。 1:
For T = [3, 0, 2, 1, 0, 2, 5, 0] the answer is [0, 2, 5].
示例编号。 2：
For T = [7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0] the answer is [0, 3, 7] or [0, 5, 7].
我不知道如何解决这个问题，我所知道的是我可能需要在这里使用一些动态规划或贪心算法，但是如何呢？有人有什么想法吗？
在决定跳到哪块石头时，我可以想到 2 个启发式方法：“尽可能远的石头”和“可能最有价值的石头”。
尽可能远的石头
- 计算到达终点所需的最小能量，比如
M，每块石头。
- 跳到最远的石头，在那里你至少可以保持石头所需的最低能量。
- 重复第 2 步，直到到达最后一块石头。
最有价值的宝石
- 计算到达终点所需的最小能量，比如
M，每块石头。
- 在每次跳跃时，计算奖励函数：
Reward of the jump (R) = Energy to be earned by the jump - Energy to be spent by the jump
在满足下一块石头的最低能量需求的情况下，跳到可能的下一块石头中奖励最高的石头。如果多颗宝石同样有价值，请选择最远的一颗。另外，如果可能的话，总是选择最后一块石头。
重复步骤 2-3 直到你到达最后一块石头。
使用 The Fartest Stone Possible 启发式的示例 2：
Idx: [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14]
T: [ 7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0]
M: [-3, 3, 2, 1, 1, 0, 2, 1, 6, 5, 4, 3, 2, 1, 0]
步骤
1。在 Idx 0 - 能量 7
-> 跳到 5，因为这是在满足最低能量需求的情况下可以得到的最远的石头。
2。在 Idx 5 - 能量 5
->跳转到7，原因同步骤1
3。在 Idx 7 - 能量 9
->跳到最后一块石头，原因同第一步
示例 2 与 可能的最有价值的石头 启发式：
Idx: [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14]
T: [ 7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0]
M: [-3, 3, 2, 1, 1, 0, 2, 1, 6, 5, 4, 3, 2, 1, 0]
步骤
1。在 Idx 0 - 能量 7
Next Idx Possible
Reward
1
-1
2
-2
3
-2
4
-4
5
-2
-> 选择 5
2。在 Idx 5 - 能量 5
Next Idx Possible
Reward
6
-1
7
4
8
-3
9
-4
10
-5
-> 选择 7
3。在 Idx 7 - 能量 9
-> 选择最后一块石头，因为有可能
请注意，最佳解决方案永远不会向后跳：在向后转向之前立即删除跳跃以使其更优，从而反驳初始解决方案的最优性。
这为我们提供了考虑位置的自然顺序。
考虑问题所在世界的状态：
- 青蛙在位置p,
- 有e能量，
- 并使用 k 跳跃到达那里。
因此，解的简单形式是：给定 p、e 和 k，有可能达到这样的境界吗？
现在，我们可以问 f(p,e,k)，它是 true 或 false，对于每一个可能的参数集，考虑前一个或下一个跳转到达这样的状态，也许会得到一个低效但可行的解决方案，递归或迭代。基础是 f(0,T[0],0) = true，期望状态是 f(n-1,?,?).
为了让它更有效率，也许我们可以让一些参数(p, e, or k) 目标函数。
例如，考虑 g(p,e) = min k：对于给定的位置和能量，计算具有这样的位置和能量的最少跳跃次数。为方便起见，定义 k 为 plus-infinity 如果这样的状态 (p,e) 无法通过任何数量的跳跃到达。
或者考虑h(p,k) = max e：如果我们到达位置p正好k次跳跃，我们还能剩余多少能量作为剩余？同样，如果 (p,k) 根本无法访问，则定义为 minus-infinity。
最后，我们甚至可以做到 a(p) = 最佳配对 (k,e)：对于给定的位置p，到达那里的最小跳跃次数k是多少，并且用这个确切的数字跳跃次数，青蛙最大剩余能量e是多少？ （也许这行不通，但思考为什么行不通仍然具有教育意义。）
考虑或扩展此列表，以确定哪种方法适合您——或者根本不适合您。
您可以使用贪心算法和优先队列在 O(n log n) 时间内解决此问题。
对于re-frame远离变长跳转的问题很有帮助
新问题框架：
- 假设您在第 0 块石头上，并且必须走完从
0 到 n-1 的 每 块石头。
- 您最初有
T[0] 当前 energy-units，每一步消耗 1 个能量单位。
- 每通过
T[i] 颗宝石，您就可以选择支付一颗 jump-dollar 并最多获得一次 T[i] energy-units。您的目标是在 jump-dollar 秒内将成本降至最低。
- 当你迈出一步时，你的能量单位不允许为零。
关键的观察是，在我们下一步真正需要这些能量之前，我们不必决定我们落在了哪些石头上（从中购买了能量）。
因此，保留我们已通过但尚未购买的所有 T[i]（energy-units 销售额）的 max-heap（priority-queue）。如果我们当前的能量是0，贪婪地移除最大的T[i]（energy-unit销售），将其添加到我们当前的能量中，并将i添加到我们的石头列表中'我从那里买了能量。
这类似于追溯决定停在 ith 石头上，这没关系，因为除了我们当前的能量和可用能量选择列表之外，没有任何影响。这种贪心算法之所以有效，是因为我们只会在不可避免的时候访问一块石头，而选择任何其他石头（而不是最高能量未使用的石头）来访问永远不会增加我们当前的能量。
Python代码（使用heapq模块）
def min_jump_path(stones: list[int]) -> list[int]:
"""Return a shortest valid path to end of the array.
We must walk from index 0 to n-1, at a cost of 1 energy unit per step.
Energy cannot be 0 when taking a step.
Runtime: O(n log n). Space: O(n)"""
used_stones: list[int] = [0]
current_energy: int = stones[0]
available_energy_choices: list[tuple[int, int]] = []
for idx, energy_offered in enumerate(stones[1:], 1):
current_energy -= 1
# If we need to use some stone's energy to continue
if current_energy < 0:
# Return some 'error-value' if impossible
if len(available_energy_choices) == 0:
return []
energy_gain, stone_used = heapq.heappop(available_energy_choices)
energy_gain = -energy_gain # Negated for max-heap
current_energy += energy_gain
used_stones.append(stone_used)
if energy_offered > 0:
heapq.heappush(available_energy_choices,
(-energy_offered, idx)) # Negated for max-heap
# Used stone list may be out of order initially
return sorted(used_stones)
用法：
print(min_jump_path([3, 0, 2, 1, 0, 2, 5, 0]))
# [0, 2, 5]
print(min_jump_path([7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0]))
# [0, 5, 7]
给定一组 n 块石头，它们以相同的距离排成一排。石头编号从 0 到 n-1。位于石号 0 的青蛙必须到达石号 n-1。
跳跃是从石头 i 到石头 j ( i<j ) 的移动。这样的跳转长度等于 j-i。青蛙的最大跳跃长度取决于它的能量水平（不能低于 0）。长度 j-i 的跳跃会消耗青蛙 j-i 的能量。例如，初始能量为 3，石头上的青蛙 0 最多可以跳到石头 3。
有些石头上可能有虫子，给青蛙补充能量。如果青蛙跳到上面有虫子的石头上，它必须吃虫子。列表 T[0...n-1] 包含相应石头上的蠕虫的能量值。如果石头上没有虫子，这个相当于0值。
青蛙开局0能量，但保证0号石上有虫。
给定一个列表 T，任务是 return 青蛙在到达石头 n-1 之前所到过的石头的索引列表。但是，这必须是最短的列表。在某些情况下，可能有不止一种解决方案，以接受者为准。保证青蛙总能到达石头n-1.
示例编号。 1:
For T = [3, 0, 2, 1, 0, 2, 5, 0] the answer is [0, 2, 5].
示例编号。 2：
For T = [7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0] the answer is [0, 3, 7] or [0, 5, 7].
我不知道如何解决这个问题，我所知道的是我可能需要在这里使用一些动态规划或贪心算法，但是如何呢？有人有什么想法吗？
在决定跳到哪块石头时，我可以想到 2 个启发式方法：“尽可能远的石头”和“可能最有价值的石头”。
尽可能远的石头
- 计算到达终点所需的最小能量，比如
M，每块石头。 - 跳到最远的石头，在那里你至少可以保持石头所需的最低能量。
- 重复第 2 步，直到到达最后一块石头。
最有价值的宝石
- 计算到达终点所需的最小能量，比如
M，每块石头。 - 在每次跳跃时，计算奖励函数：
Reward of the jump (R) = Energy to be earned by the jump - Energy to be spent by the jump
在满足下一块石头的最低能量需求的情况下，跳到可能的下一块石头中奖励最高的石头。如果多颗宝石同样有价值，请选择最远的一颗。另外，如果可能的话，总是选择最后一块石头。
重复步骤 2-3 直到你到达最后一块石头。
使用 The Fartest Stone Possible 启发式的示例 2：
Idx: [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14]
T: [ 7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0]
M: [-3, 3, 2, 1, 1, 0, 2, 1, 6, 5, 4, 3, 2, 1, 0]
步骤
1。在 Idx 0 - 能量 7
-> 跳到 5，因为这是在满足最低能量需求的情况下可以得到的最远的石头。
2。在 Idx 5 - 能量 5
->跳转到7，原因同步骤1
3。在 Idx 7 - 能量 9
->跳到最后一块石头，原因同第一步
示例 2 与 可能的最有价值的石头 启发式：
Idx: [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14]
T: [ 7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0]
M: [-3, 3, 2, 1, 1, 0, 2, 1, 6, 5, 4, 3, 2, 1, 0]
步骤
1。在 Idx 0 - 能量 7
| Next Idx Possible | Reward |
|---|---|
| 1 | -1 |
| 2 | -2 |
| 3 | -2 |
| 4 | -4 |
| 5 | -2 |
-> 选择 5
2。在 Idx 5 - 能量 5
| Next Idx Possible | Reward |
|---|---|
| 6 | -1 |
| 7 | 4 |
| 8 | -3 |
| 9 | -4 |
| 10 | -5 |
-> 选择 7
3。在 Idx 7 - 能量 9
-> 选择最后一块石头，因为有可能
请注意，最佳解决方案永远不会向后跳：在向后转向之前立即删除跳跃以使其更优，从而反驳初始解决方案的最优性。 这为我们提供了考虑位置的自然顺序。
考虑问题所在世界的状态：
- 青蛙在位置p,
- 有e能量，
- 并使用 k 跳跃到达那里。
因此，解的简单形式是：给定 p、e 和 k，有可能达到这样的境界吗？
现在，我们可以问 f(p,e,k)，它是 true 或 false，对于每一个可能的参数集，考虑前一个或下一个跳转到达这样的状态，也许会得到一个低效但可行的解决方案，递归或迭代。基础是 f(0,T[0],0) = true，期望状态是 f(n-1,?,?).
为了让它更有效率，也许我们可以让一些参数(p, e, or k) 目标函数。
例如，考虑 g(p,e) = min k：对于给定的位置和能量，计算具有这样的位置和能量的最少跳跃次数。为方便起见，定义 k 为 plus-infinity 如果这样的状态 (p,e) 无法通过任何数量的跳跃到达。
或者考虑h(p,k) = max e：如果我们到达位置p正好k次跳跃，我们还能剩余多少能量作为剩余？同样，如果 (p,k) 根本无法访问，则定义为 minus-infinity。
最后，我们甚至可以做到 a(p) = 最佳配对 (k,e)：对于给定的位置p，到达那里的最小跳跃次数k是多少，并且用这个确切的数字跳跃次数，青蛙最大剩余能量e是多少？ （也许这行不通，但思考为什么行不通仍然具有教育意义。）
考虑或扩展此列表，以确定哪种方法适合您——或者根本不适合您。
您可以使用贪心算法和优先队列在 O(n log n) 时间内解决此问题。
对于re-frame远离变长跳转的问题很有帮助
新问题框架：
- 假设您在第 0 块石头上，并且必须走完从
0到n-1的 每 块石头。 - 您最初有
T[0]当前 energy-units，每一步消耗 1 个能量单位。 - 每通过
T[i]颗宝石，您就可以选择支付一颗 jump-dollar 并最多获得一次T[i]energy-units。您的目标是在 jump-dollar 秒内将成本降至最低。 - 当你迈出一步时，你的能量单位不允许为零。
关键的观察是，在我们下一步真正需要这些能量之前，我们不必决定我们落在了哪些石头上（从中购买了能量）。
因此，保留我们已通过但尚未购买的所有 T[i]（energy-units 销售额）的 max-heap（priority-queue）。如果我们当前的能量是0，贪婪地移除最大的T[i]（energy-unit销售），将其添加到我们当前的能量中，并将i添加到我们的石头列表中'我从那里买了能量。
这类似于追溯决定停在 ith 石头上，这没关系，因为除了我们当前的能量和可用能量选择列表之外，没有任何影响。这种贪心算法之所以有效，是因为我们只会在不可避免的时候访问一块石头，而选择任何其他石头（而不是最高能量未使用的石头）来访问永远不会增加我们当前的能量。
Python代码（使用heapq模块）
def min_jump_path(stones: list[int]) -> list[int]:
"""Return a shortest valid path to end of the array.
We must walk from index 0 to n-1, at a cost of 1 energy unit per step.
Energy cannot be 0 when taking a step.
Runtime: O(n log n). Space: O(n)"""
used_stones: list[int] = [0]
current_energy: int = stones[0]
available_energy_choices: list[tuple[int, int]] = []
for idx, energy_offered in enumerate(stones[1:], 1):
current_energy -= 1
# If we need to use some stone's energy to continue
if current_energy < 0:
# Return some 'error-value' if impossible
if len(available_energy_choices) == 0:
return []
energy_gain, stone_used = heapq.heappop(available_energy_choices)
energy_gain = -energy_gain # Negated for max-heap
current_energy += energy_gain
used_stones.append(stone_used)
if energy_offered > 0:
heapq.heappush(available_energy_choices,
(-energy_offered, idx)) # Negated for max-heap
# Used stone list may be out of order initially
return sorted(used_stones)
用法：
print(min_jump_path([3, 0, 2, 1, 0, 2, 5, 0]))
# [0, 2, 5]
print(min_jump_path([7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0]))
# [0, 5, 7]