牛客网 -- 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;j<approximate.size();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])<<endl;return 0;
}

你学会了吗？？？