解法框架

待定

跳石板

動態規劃——有很多解，但是要求最優的那一個。動態規劃的核心思想就是已經解決的問題要能被后面所利用。

采用下面的思維導圖，梳理以下過程。跳石板的時候每次能跳得距離只能是當前石板的編號的約數（除了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;}

總結

以上是生活随笔為你收集整理的动态规划之跳石板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。