跳石板-动态规划

痛定思痛。 2022-06-09 09:22 160阅读 0赞

## 题目描述 ##

小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3.......  
这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的 石板，小易单次只能往前跳K的一个约数(不含1和K)步，即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板，他想跳到编号恰好为M的石板去，小易想知道最少需要跳跃几次可以到达。  
例如：  
N = 4，M = 24：  
4->6->8->12->18->24  
于是小易最少需要跳跃5次，就可以从4号石板跳到24号石板

## 输入描述: ##

输入为一行，有两个整数N，M，以空格隔开。
    (4 ≤ N ≤ 100000)
    (N ≤ M ≤ 100000)

## 输出描述: ##

输出小易最少需要跳跃的步数,如果不能到达输出-1

示例1

## 输入 ##

4 24

## 输出 ##

## 5 ##

#include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    #define INT_MAX 100001
    int main()
    {
    	int n, m;
    	while(cin >> n >> m)
    	  {
    		 vector<int> dp(m + 1, INT_MAX);  //dp[i]为在第i个石板时，所需要的步数，初始设为条件范围内的最大值
    		 dp[n] = 0;
    		 for (int i = n; i <= m; i++)
    			{
    			 for (int j = 2; j*j <= i; j++)   //比如i为8，当找到i的一个约数j为2时，另一个约数就为i/j
    			    {                             //所以只需要找j*j<=i,事实上如果不这样做，部分用例运行超时
    				 if (i%j == 0)
    					{
    					  if (i + j <= m)
    						 dp[i + j] = min(dp[i + j],dp[i]+1);
                          if(i+i/j<=m) //关键步骤
                             dp[i + i/j] = min(dp[i + i/j],dp[i]+1);
    					}
    			    }
               }
           if(dp[m]==INT_MAX)
               cout<<"-1"<<endl;
           else
               cout<<dp[m]<<endl;
    	 }
    }