Step Stones

跳石板，这是网易校招的一道编程题，很显然这是一个最优化的问题，由于在平常也没真正练习这些经典算法题，所以拿到题目手足无措，一开始的思路就是递归，递归是能够找到最小值，但是效率好像不理想，很显然自己搞不下去了，忽视了核心问题就是分解后的子问题不是相互独立的，而是互相有关联的。
算法基础是动态规划，这是常用的最优化算法之一。
递归与动态规划小结不错~

题目描述

小易来到了一条石板路前，每块石板上从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.创建一维数组，用于存储从起点到达改点的最小跳跃次数；
– 初试起点为0，其它元素均为int最大值，用来表示不可达

# init a dictionary to store the count
import sys
stone = {}
stone[N] = 0
for i in range(N+1, M+1):
    stone[i] = sys.maxint   # the maximum int

2.遍历每一块石板，然后求解当前石板的约数（列表），针对每个约数可以求解从当前石板可以到达的石板编号，且能够获取从当前石板到达的石板的跳跃次数；
– 后一步石板最小跳跃次数求解：如果后一步的石板次数是初始化的最大值，则在当前石板达到的跳跃次数基础上加1，否则与后一步石板的跳跃次数做比较，求两者中的最小者；
1
2
3
4
5
6
7
8
9
if N == M:
        return stone[M]
    else:
        # 针对每一个石块，计算其能到达的石块，然后每个石块都保留了到达此处需要的步数，每次遍历都保留最小值，即最少需要的步数
        for i in range(N, M+1):
            divisors = calDivisors(i)
            for j in divisors:
                if i + j <= M:
                    stone[i + j] = min(stone[i] + 1, stone[i + j])
附：求解一个数的所有约数
1
2
3
4
5
6
7
8
# calculate all divisors without 1 and self for a given number in the natural range
def calDivisors(N):
    divisors = []
    for i in range(2, int(N / 2.0)+1):   # 此处如果是sqrt(N)， 应该求解的不是所有约数？
        if N % i == 0:
            divisors.append(i)
    # divisors.append(N)
    return divisors

保留完整路径

以上是能够找到从一个石板调到另外一个石板的最小跳跃次数，但是有时候希望能够保留这个最小路径，即跳跃过程是怎样的？所以需要对上述过程进行略微修改~

在进行跳跃次数计数的后面紧接着记录调到下一个石板的这一块石板编号，这样就记录了一个连续的过程，即记录了跳到某块石板的前一块石板编号，如“24：18”，即跳到编号为24的石板的前一块石板编号是18。
所以增加一行代码：

1	stoneIndex.append(str(i+j) + "：" + str(i)) # 存储到达 i+j 石块的石块编号

打印输出：

1	print "; ".join(stoneIndex)

输出结果为：
6：4; 8：6; 9：6; 10：8; 12：8; 12：9; 12：10; 15：10; 14：12; 15：12; 16：12; 18：12; 16：14; 21：14; 18：15; 20：15; 18：16; 20：16; 24：16; 20：18; 21：18; 24：18; 22：20; 24：20; 24：21; 24：22
其中只有一条可以最少跳跃数完成：
4 -> 6 -> 8 -> 12 -> 18 -> 24