牛客网 跳石板
题目：跳石板
题目描述
小易来到了一条石板路前，每块石板上从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，以空格隔开。 (4 ≤ N ≤ 100000) (N ≤ M ≤ 100000)输出描述:
输出小易最少需要跳跃的步数,如果不能到达输出-1示例1
输入
4 24输出
5自己的解法思路为：建立一个M+1的数组，数组元素为-1，N位置为0，获取N的约数，并且前进，对应到达位置设置为当前步数，代码如下，复杂度过高，没有提交成功：
N,M=[int(each) for each in input().split()]
def getNYueShu(n):
mid=n//2
result=[]
for i in range(2,mid+1):
if i not in result:
# 判断是否是约数
if n%i==0:
result.append(i)
j=int(n/i)
if j not in result:
result.append(j)
return result
def getCounts(N,M):
# ys=getNYueShu(N)
# ys=sorted(ys,reverse=True)
count=0
step=[-1]*(M+1)
step[N]=0
cur_val=[N]
while cur_val:
next=[]
count+=1
#print(count)
for j in cur_val:
ys=getNYueShu(j)
ys = sorted(ys, reverse=True)
for i in ys:
if j+i<=M and i+j not in next:
next.append(i+j)
tmp_next=[]
for n in next:
if step[n]==-1:
step[n]=count
tmp_next.append(n)
if n==M:
break
cur_val=tmp_next
return step[M]
print(getCounts(N,M))参考解法：跳石板
def solution(n, m):
divs = [[] for _ in range(m + 1)]
for i in range(2, m + 1):
t=[j for j in range(i + i, m + 1, i)]
for j in range(i + i, m + 1, i):
divs[j].append(i)
value = [m] * (m + 1)
value[n] = 0
for i in range(n, m + 1):
if value[i] < m:
for x in divs[i]:
if i + x < m + 1:
value[i + x] = min([value[i + x], value[i] + 1])
if value[m] < m:
return value[m]
else:
return -1
data = [int(i) for i in input().strip().split()]
n = data[0]
m = data[1]
print(solution(n, m))理解的思路是：先求出可达位置的约数，然后在接下来的for循环中去设定每个可达位置的最短步数
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年08月28日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录