所用到的知識

STL中的vector容器
動態規劃思想
算法中的min

編程思想

將1 - M個看成一排，為其取個名字叫Slab（數組），并在走之前將這一排石板都初始化為0，然后開始走，每到一塊是班上就在這塊是石板上寫下到這里來的步數，如果腳下踩的這塊石板上寫的0，說明之前沒有來過，那就不可能走到這里，跳過這個石板，重新走
2. 從起點開始對這一排石板Slab進行遍歷，求出可以從這塊石板出發走的步數（當前石板對應位置的所有約數）

到達當前位置就要更新這塊石板的上面寫的步數，選擇之前走的步數和現在走的步數中最小的卸載當前是石板上，如果之前沒有到達過這塊石板則更新為此時位置的最小步數 + 1，
4. 知道走到最后一塊石版，或者下一次將要走到最后一塊石板的時候，看之前有沒有到過最后一塊石板，如果有，就返回上面的步數（Slab[m]），如果沒有就要返回-1

接下來就直接上代碼，代碼中也有注釋

#include <iostream> #include <vector> #include <algorithm>using namespace std;//計算該數的公約數 void Divisor(int n,vector<int>& buff) {for(size_t i = 2; i <= sqrt(n); ++i){if(n%i == 0){buff.push_back(i);//如果這個數不是平方數，那么也將另一個數加入到列表中if(n/i != i)buff.push_back(n/i);}} }int Jump_Slab(int n, int m) {//存放從起始位置到每個位置所需要的步數vector<int> Slab(m+1,0);//從n位置走到n位置只需要1步，所以初始化為1Slab[n] = 1;for(size_t i = n; i < m; ++i){//如果這個位置為0，說明不能走到這個位置，跳出此次循環if(0 == Slab[i])continue;//存放i位置可以走的步數vector<int> Jump;Divisor(i,Jump);//Slab[Jump[j] + i]是當前可以走到的位置for(size_t j = 0; j < Jump.size(); ++j){//由位置i出發能到達的點為 stepNum[divNum[j]+i]if(Jump[j] + i <= m && Slab[Jump[j] + i] != 0)//如果到達了這次可以走到的地方沒有超過M點，//并且這個位置已經來過，要取從起點到這個位置的步數和現在要更新的步數最少的Slab[Jump[j] + i] = min(Slab[Jump[j] + i], Slab[i]+1);else if(Jump[j] + i <= m)///將可以走的位置更新，由于是在i位置開始走的下一步，//所以走到這里的步數在i位置的基礎上加一Slab[Jump[j] + i] = Slab[i]+1;}}if(0 == Slab[m])return -1;elsereturn Slab[m] -= 1; }int main() {int n,m;cin >> n >> m;cout << Jump_Slab(n,m) << endl;return 0; }

總結

以上是生活随笔為你收集整理的跳石板（通俗易懂的思路和方法）的全部內容，希望文章能夠幫你解決所遇到的問題。

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