题解 | #跳石板#

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

vector<int> GetDiv(int n)//求约数组合
{
    vector<int> t;
    for(int i = 2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            t.push_back(i);
            if(i*i!=n)
            {
                t.push_back(n/i);
            }
        }
    }
    return t;
}


int main() {
    int n,m;
    cin>>n>>m;
    vector<int> dp(m-n+1,m+1);//设置一个不可能的最大次数

    dp[0] = 0;
    for(int i = n;i<m;i++)
    {
        int sub = i-n;
        if(dp[sub]<m+1)//跳到的才去检查
        {
            vector<int> div = GetDiv(i);
            for(auto num:div)
            {
                if(sub + num<=m-n)//防止越界
                {
                    dp[sub+num] = (dp[sub]+1)<dp[sub+num]?(dp[sub]+1):dp[sub+num];
                }
            }
        }
    }
    if(dp[m-n]==m+1)
    {
        cout<<-1;
    }
    else {
        cout<<dp[m-n];
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

花了好久时间，发现自己对动态规划的理解可以说不到位吧。

初始化动态规划，这个题里面如果初始化合理，省去一次判断，省下时间不说，也少了麻烦。

然后就是为了访问，动态规划不是非得要去整个连续的。

关于动态规划就是这点心得，动态规划本质就是递推，因此初始化正确的默认值，是很重要的。

2.求约数直接一次双取，之前没有如此导致时间复杂度过高。