跳石板 动态规划 22行python实现 |算法

发布于 2021-07-10  23 次阅读


我的csdn文章链接:https://blog.csdn.net/LLLLQZ/article/details/116484419

题目

小易来到了一条石板路前,每块石板上从1挨着编号为:1、2、3…
这条石板路要根据特殊的规则才能前进:对于小易当前所在的编号为K的 石板,小易单次只能往前跳K的一个约数(不含1和K)步,即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板,他想跳到编号恰好为M的石板去,小易想知道最少需要跳跃几次可以到达。

例如:
N = 4,M = 24:
4->6->8->12->18->24
于是小易最少需要跳跃5次,就可以从4号石板跳到24号石板

思路

根据动态规划的思想,我们可以将N~M个石板看做成一个列表step[i],其中列表中每一个元素都存储着N到当前位置的最小步数,我们之后把step[M]输出,即M到N的最小步数

那实现过程有几个问题需要解决
1、首先是为什么要列表中存储着N到当前位置的最小步数
因为根据动态规划而言,当前k状态跟前k-1状态有关,而且前k-1状态有关
因此我们如果要找到N到M的最小步数,我们得找到N到前面石板的的最小步数,也就是对于DP而言,每一步都是最优。

2、我们怎么让列表每一个元素存储N到当前位置的最小步数
我们通过遍历的方式让列表存储N到当前位置的步数,这样势必会遇到同一块石板有不同的步数到达,这时候就需要我们进行选择了,选择之前的到达该石板步数和当前步数+1两者最小的,这就是我们的动态规划状态转移方程

step[i+j]=min(step[i]+1,step[i+j])
step[N]=0

​3、遍历过程中有些点我们不需要经过,该怎么处理
比如4到24中 5,7等位置不需要经过,我们解决方式是先把列表全初始化为MAX(65535),然后把N位置值设置为0(因为N是开始点,步数为0),之后由于每次经过的点都会赋予步数值,没有经过的仍然为MAX,我们设置

if step[i] == MAX:
continue

便可以跳过未经过位置

代码实现

MAX = 65535
if __name__ == '__main__':
    N = int(input())  # 起始跳板
    M = int(input())  # 终点跳板
    step = [MAX for value in range(0,M+1)]
    step[N] = 0
    for i in range(N,M+1):
        if step[i] == MAX:
            continue
        for j in range(2,i):
            if pow(j,2)>i:
                break
            if i % j == 0:
                if i+j <= M:                //约数1
                    step[i+j]=min(step[i]+1,step[i+j])
                if i + (i // j) <= M:        //约数2
                    step[i+(i//j)]=min(step[i]+1,step[i+(i//j)])

    if step[M] == MAX:
        print("无最少跳跃次数")
    else:
        print(f"跳跃次数为{step[M]}")