[算法题] 跳一跳 Python求解

题目描述：跳一跳

​ 有一条石板路，每块石板上从1挨着编号为：1、2、3…，这条石板路要根据特殊的规则才能前进：对于当前所在的编号为 K 的石板，单次只能往前跳K的一个约数(不含1和 K )步，即跳到 K + X ( X 为 K 的一个非1和本身的约数)的位置。若当前处在编号为 N 的石板，想跳到编号恰好为 M 的石板去，请求解最少需要跳跃次数，不可到达输出-1。

​ 输入格式：4 24

​ 输出格式：5

算法设计思路

求解过程中涉及到两个方面的问题，一个是每个点能取到的约数，另一个则是得到每个点最优的需要跳跃次数。

对于前一个问题，先找出终点final之前的所有点能得到的除了自身和1以外的最大的约数 i，之后对这个数向2遍历，并基于该数计算最小可能约数 j 向终点遍历进行判断，以此判断确认终点之前的点可取的约数（除了1和自身）是否包括该数。若包括，则使用列表 T[ j ] 进行保存。该步骤之后得到的列表 T 代表的是汇总了终点前各个点的约数（除1和自身）列表的列表。

对于后一个问题，我先将各个点到达终点的跳跃数置为-1，并利用列表 dp 保存。同时，将终点到终点的距离置为0，即 dp[ final ] = 0。接下来，从终点前一个点向起点遍历，对某个点 i 处理时，对 i 可取的约数 k 进行遍历，有下面几种情况：

1. 若 i + k 大于终点 final，则表示这样跳跃越过终点，不满足题意，尝试下一个约数 k’；
2. 我用 v 记录由点 i 跳跃到 i + k，再跳跃到终点所需的跳跃数，则有 v = dp [i + k] + 1，若 v 为0，则说明 dp[ i + k ]为-1，此时表示由点 i + k 无法到达终点，故而该约数不可取，该尝试下一个约数；
3. 若通过前述两条规则判断，则说明可经由 i 点跳转到 i + k 再跳转到终点，此时，如果 dp[ i ]为-1，则表示先前并未对该值进行更新，则令 dp[ i ] = v 对 dp[ i ]做更新；
4. 如若 dp[ i ]已有值且 v 小于该值，则说明目前的 v 为更少跳跃数的方案，应利用 v 对dp[ i ]进行更新；如若不然，则应该保留已有正值的 dp[ i ]。

最终，返回 dp[ start ]即为起点跳跃到终点的最少跳跃次数。

代码实现

import itertools  # 用于初始化dp数组

def jump(start, final):
    dp = [x for x in itertools.repeat(-1, final + 1)]  # 用于存放每个点到达终点的最小跳跃数，初始时为-1
    T = [[] for x in itertools.repeat(None, final)]    # 用于存放每个点的所有因数
    dp[final] = 0             # 终点距离终点不需要跳跃，故置为0
    i = (final - 1) // 2      # 从比终点小的点不包含自身的因数里最大的因数往下循环
    while i > 1:              # 所留因数不包含1
        j = i * 2             # 从因数i的最小可能约数往上循环
        while j < final:      # 所留因数不含自身
            if (j % i == 0):                   # 判断i是否为j的因数，是则存入
                T[j].append(i)
            j += 1
        i -= 1

    # 求完因数后，更新dp
    i = final - 1  # 从final - 1点往start遍历更新dp
    while i >= start:
        for k in T[i]:
            if (i + k > final):  # 若越过终点，则不可取。换下一种
                continue
            v = dp[i + k] + 1    # v表示由i跳到i + k后再跳到终点的跳跃数
            if v == 0:           # 意味着跳到i + k点后不可达终点，换下一种
                continue
            # 经过上述条件仍在循环内的点都是能到达终点的点
            if dp[i] == -1:      # 以能够到达的跳跃数更新初始值
                dp[i] = v
            elif v < dp[i]:      # 以更优的跳跃数更新已有值
                dp[i] = v
        i -= 1
    return dp[start]

N, M = [int(x) for x in input().split()]
print(jump(start = N, final = M))

运行结果

​当起点为4，终点为24时：

当起点为10，终点为26时：

验证结果后所得确实正确​~​

本文地址：https://blog.csdn.net/some_apples/article/details/107585047