网易2017年秋季校招编程题，在牛客网上刷题通过，下面记录相关思路。
题目描述
小易来到了一条石板路前，每块石板上从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
输入描述
输入为一行，有两个整数N，M，以空格隔开。
(4 ≤ N ≤ 100000)
(N ≤ M ≤ 100000)
输出描述
输出小易最少需要跳跃的步数,如果不能到达输出-1
示例
输入
4 24
输出
5
问题分析
从起点到终点的距离是不变的，若要跳跃次数最少，则每次跳所能跳的最大步数，是不是跳跃次数就最少呢？这是一种贪心法的思想。众所周知，贪心算法不一定能得到最优解，但却是一个可行的、较好的解。如果用贪心法来求解此题，具体的思路为：每次跳跃都选取最大的约数，若后续发生不可到达点（编号为素数），则进行回溯，取第2大的约数作为前进的步数。
如何求得最优解，需要换一个角度考虑。对于一条路径，若使得从起点出发到达途中每一个点的跳跃次数最小，那么最终到达终点时跳跃总次数最小，这就是动态规划的思想，而最终得到的解就是最优解。对于途中的一个点，从起点出发到该点能到达的点（以该点编号约数为步数）有两种选择，经过该点或者不经过该点，那么跳跃次数就有两种情况，原有的到能到达的点的跳跃次数和到该点的跳跃次数加1（从该点可以直接跳到能到达的点，故而加1），选取较小的一个即可。可得状态转移方程为：
i为石板编号，j为i的约数，N为起点编号
dp[i+j] = min(dp[i]+1, dp[i+j])
dp[N] = 1
程序代码
代码采用C++编写，运行在clang++ 3.3环境中。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
using namespace std;
// 求约数，不包括1和它本身
void div(int n, vector<int> & arr)
{
for(int i = 2; i <= sqrt(n); i++)
{
if(n % i == 0)
{
arr.push_back(i);
if(n / i != i)
arr.push_back(n / i);
}
}
}
int main()
{
int n, m;
cin >> n >> m;
// dp[i]表示从起点出发到达编号为i的石板所需跳跃的最少次数
// 初始化为0，表示无法从起点到达该点
vector<int> dp(m + 1, 0);
vector<int> divs;
// 起点设置为1，区别于其它点
dp[n] = 1;
// 对于起点之后的每一个点依次规划求解
for(int i = n; i <= m; i++)
{
// 若无法到达该点，舍弃该点
if(!dp[i])
continue;
// 获取该点编号的约数
divs.clear();
div(i, divs);
// 对每个能到达的点更新最小次数
for(int j = 0; j < divs.size(); j++)
{
// divs[j]表示在点i处，一次跳跃能够前进的步数
// 跳跃后到达的点为i + divs[j]，若小于终点编号则能一次到达
if(i + divs[j] <= m)
{
// 落下的点最小次数非0，则在点i之前存在另一条次数最少的路径
// 故该点的最小次数有两种选择：原值、点i最小次数+1（从点i跳过去）
// 若要最终结果最小，则取二者中较小的
if(dp[i + divs[j]])
dp[i + divs[j]] = min(dp[i + divs[j]], dp[i] + 1);
// 最小次数为0，表示之前并不存在别的路径
// 则该点的最小次数仅有点i最小次数+1（从点i跳过去）这一种选择
else
dp[i + divs[j]] = dp[i] + 1;
}
}
}
// 最终解需减去起点的次数1
cout << (dp[m] > 0 ? dp[m] - 1 : -1);
return 0;
}