解法框架

待定

跳石板

动态规划——有很多解，但是要求最优的那一个。动态规划的核心思想就是已经解决的问题要能被后面所利用。

采用下面的思维导图，梳理以下过程。跳石板的时候每次能跳得距离只能是当前石板的编号的约数（除了1和本身）。

下图中，已经把从4跳到24的所有可能情况列了出来（由于篇幅限制，所以像7,11等这种情况就忽略了），用一个数组step保存从4开始到达每个石板数字的步数，比如step[8]=3，表示从4跳到8需要三步（这里把自己跳到自己身上算作1次），在初始情况下，除了step[4]=1（step[4]设置为1）之外的所有数字，全部设为一个很大的数，表示不可到达（下面思维导图中，用恶魔头像表示）

• 括号中的数字表示到达该数字的步数

首先从4开始，对于4来说，只有一个约数2，所以它只能跳到6，当它的来到6之前需要进行判断：一是到达的石板编号是否已经超越了目标石板编号，二是到达的石板是否为max，即是否是不可到达。所以这里到达6之后，判断第二个条件，6它是一个不可到达的石板，那么我们就直接就step[6]=step[4]+1，表示只需一步

来到6之后，它有两个选择，分别可以到达8和9，所以按照上述步骤，继续更新

对于8也是如此，对于9也是一样

所以大家可以发现，位于同一层级其实就表示步数是相同的，在当前情况下，走哪一条都可以

对于10，当他来到12时，此时由于之前8已经将12给更新了，所以从10到达12时，进行判断时m，12不是不可到达的一个石板，而是有确定的编号的，即step[12]=4，因此10在更新12时要进行一个比较：step[10+2]小还是step[10]+1小，很明显这里step[10+2]=step[12]=4<step[10]+1=4+1<5，因此step[12]继续保持为4，同时由10到12再到24这一条路线其实已经就pass了

接下来的过程就是重复上述过程了

代码

首先写出基本框架

#include <iostream> #include <vector> #include <math.h> #include <limits.h> using namespace std;int Jump(int N,int M) {return 0;}int main() {int N,M;//起始石板编号和终止石板编号cin>>N>>M;cout<<Jump(N,M)<<endl;}

第二步编写Jump函数

• 建立一个step数组，用来存储到达某一个点的步数，比如step[8]=3，表示从4到8需要2步（因为step[4]设置为1）
• 初始化step数组，除了起始点外，其余均设置为INT_MAX（头文件为limits.h）
• for循环从N到M跳跃，遍历时如果某个点，比如step[i]==INT_MAX表示此点不可达，直接下一个.
• 中间编写一个函数用于获取当前石板的所有约束，存储在一个数组当中，然后遍历这个数组，判断方法和上面的图中展示时一致的

#include <iostream> #include <vector> #include <math.h> #include <limits.h> using namespace std;void getdiv(int n,vector<int>& div) {for(int i=2;i<=sqrt(n);i++){if(n%i==0){div.push_back(i);if((n/i)!=i)//非平方数注意不要忽略div.push_back(n/i);}} }int Jump(int N,int M) {vector<int> step(M+1,INT_MAX);//放置越界，初始化M+1大小step[N]=1;//自己跳到自己算1步，其实这里为0也可以，最后反悔的时候不用减1即可for(int i=N;i<M;i++){if(step[i]==INT_MAX)//这个点不可达，continuecontinue;vector<int> div;//用于获取i的约数getdiv(i,div);for(int j=0;j<div.size();j++)//动态规划核心代码{if((div[j]+i)<=M && step[i+div[j]]!=INT_MAX)//i+div[j]这个石板不等于INT_MAX，表示肯定已经走过了而且保存的是最小值{step[i+div[j]]=min(step[i+div[j]],step[i]+1);}else if((div[j]+i)<=M)//不可达step[i+div[j]]=step[i]+1;}}if(step[M]==INT_MAX){return -1;}elsereturn step[M]-1;//起始位置是1开始的 }int main() {int N,M;//起始石板编号和终止石板编号cin>>N>>M;cout<<Jump(N,M)<<endl;}

总结

以上是生活随笔为你收集整理的动态规划之跳石板的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。