题解 | #跳石板#C++解法 动态规划

#include <climits>
#include <iostream>
#include <vector>
using namespace std;

//求约数
void get_y(vector<int>& v, int x) {
    for(int i = 2; i * i <= x; i++) {
        if(x % i == 0) {
            v.push_back(i);
            if(x / i != i)
            v.push_back(x / i);
        }
    }
}

int jump(int n, int m) {
    vector<int> step(m + 1, INT_MAX);
    step[n] = 0;//初始化第一个位置
    for(int i = n; i < m; i++) {
        if(step[i] == INT_MAX) continue;
        vector<int> v;//存约数
        get_y(v, i);
        for(int j = 0; j < v.size(); j++) {
            //如果不是第一次到这里
            if(i + v[j] <= m && step[i + v[j]] != INT_MAX) {
                //新的和旧的比较谁的步数少
                step[i + v[j]] = step[i + v[j]] > step[i] + 1 ? step[i] + 1 : step[i + v[j]];
            }
            else if(i + v[j] <= m) {
                //如果是第一次来就直接赋值
                step[i + v[j]] = step[i] + 1;
            }
        }
    }
    //如果该位置被赋值，证明找到了，返回该位置的值即可
    return step[m] == INT_MAX ? -1 :step[m];
}

int main() {
    int n, m, min_step;
    cin >> n >> m;
    min_step = jump(n, m);
    cout << min_step << endl;
    return 0;
}