每天一道编程题——跳石板

Code

小易来到了一条石板路前，每块石板上从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

输入例子:
4 24

输出例子:
5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from math import sqrt
# 求约数
def divisor(i):
    l = []
    for j in range(2, int(sqrt(i)) + 1):
        if i % j == 0:
            l.append(j)
            if i / j != j:
                l.append(i / j)
    return l
nf = 99999
def func(N, M):
    dp = [inf] * (M + 1)
    if N == M: return 0
    dp[N] = 0
    for i in xrange(N, M + 1):
        if dp[i] == inf: continue
        divisors = divisor(i)
        for j in divisors:
            if i + j <= M:
                # 保留最小步数
                dp[i + j] = min(dp[i + j], dp[i] + 1)
    return -1 if dp[M] == inf else dp[M]

来自网易2017秋招

本文标题:每天一道编程题——跳石板

文章作者:Vincent Zhong

发布时间:2016-09-29, 22:47:53

最后更新:2019-07-07, 13:13:09

原始链接:https://wax8280.github.io/2016/09/29/每天一道编程题——跳石板/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
|