牛客网 -- WY28 跳石板

题目链接： 跳石板_牛客题霸_牛客网 (nowcoder.com)

解题步骤：

参考代码：

void get_approximate(vector<int>& v,int n)
{
    //求约数，从2到sqrt(n)即可，原因看图解
    //这里一定要等于sqrt(n)，例如16，4也是约数
    for(int i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
            v.push_back(i);
            //i是n的约数，那么n/i也是n的约数
            //但是如果i==n/i，即重复的就取一个就好
            //不等的时候两个都要取
            if(n/i!=i)
            {
                v.push_back(n/i);
            }
        }
    }
}
 
int main()
{
    int n=0;
    int m=0;
    cin>>n>>m;
    //多开一行，多开一列，并初始化为最大值
    vector<int> dp(m+1,INT_MAX);
    //初始化dp[n]的值
    dp[n]=0;
    for(int i=n;i<=m;i++)
    {
        if(dp[i]==INT_MAX)//说明i位置不可到达，直接continue
        {
            continue;
        }
        vector<int> approximate;
        //获取i的所有约数
        get_approximate(approximate,i);
        //填写dp表中所有dp[i+i的约数]的值
        for(int j=0;jsize();j++)
        {
            //i+approximate[j]<=m才有必要更新
            //状态转移方程
            if(i+approximate[j]<=m&&dp[i+approximate[j]]==INT_MAX)
            {
                dp[i+approximate[j]]=dp[i]+1;
            }
            else if(i+approximate[j]<=m&&dp[i+approximate[j]]!=INT_MAX)
            {
                dp[i+approximate[j]]=min(dp[i+approximate[j]],dp[i]+1);
            }
        }
    }
    //判断dp[m]是否符合题意
    cout<<(dp[m]==INT_MAX?-1:dp[m])<
 
    return 0;
}

你学会了吗？？？