牛客12576题解：动态规划解决因数跳跃问题

一、问题描述

牛客12576题要求计算从数字N跳到数字M的最少步数，每次跳跃只能跳当前数字的真因数（不包括1和自身）的距离。若无法到达则返回-1。

二、算法核心思想

采用动态规划方法：

1. 预处理每个数字的真因数

2. 初始化DP数组记录到达每个数字的最小步数

3. 通过状态转移更新可达数字的步数

4. 最终输出目标数字的步数

三、完整代码实现（带注释）

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

// 获取数字n的所有真因数（不包括1和n本身）
vector<int> getJumps(int n) {
    vector<int> res;
    if(n <= 1) return res;  // 1及以下数字没有真因数
    for(int i=2; i*i<=n; ++i) {  // 只需遍历到sqrt(n)
        if(n%i == 0) {  // 找到因数
            res.push_back(i);
            if(i != n/i) res.push_back(n/i);  // 避免重复添加平方数
        }
    }
    return res;
}

int main() {
    int N, M;
    cin >> N >> M;
    if(N == M) {  // 特殊情况处理
        cout << 0 << endl;
        return 0;
    }
    
    // 初始化DP数组，dp[i]表示到达i的最小步数
    vector<int> dp(M+1, INT_MAX);
    dp[N] = 0;  // 起点步数为0
    
    for(int i=N; i<=M; ++i) {
        if(dp[i] == INT_MAX) continue;  // 跳过不可达的点
        
        vector<int> jumps = getJumps(i);  // 获取当前数字的所有真因数
        for(int jump : jumps) {
            if(i + jump > M) continue;  // 跳过超出范围的情况
            dp[i+jump] = min(dp[i+jump], dp[i]+1);  // 状态转移
        }
    }
    
    cout << (dp[M]==INT_MAX ? -1 : dp[M]) << endl;
    return 0;
}

四、关键点解析

1. 因数获取优化：

• 只需遍历到sqrt(n)即可找到所有因数

• 避免重复添加平方数的因数

2. 动态规划初始化：

• 使用INT_MAX表示不可达状态

• 起点N的步数初始化为0

3. 状态转移：

• 只处理可达的数字

• 检查每个因数跳跃是否超出范围

• 更新目标位置的最小步数

五、扩展思考

1. 如何优化大范围(M>>N)的情况？

2. 如果允许跳1会怎样影响算法？

3. 如何记录具体跳跃路径？

4. 如何处理带权重的因数跳跃？