使用递归到达序列末尾的最小跳转次数

Question

我有一个“使用递归到达数组末尾的最小跳跃次数”的代码。但我无法打印序列。（vector vec中没有可打印的内容）
如有任何帮助，将不胜感激。

说明：
我想以最小跳跃从数组的第一个元素（即2）到达最后一个元素（即4）
跳转的方式：
第一个元素是2。这意味着我最多可以在阵列中进行2次跳跃。如果我跳第一步，那么我可以跳到第二个元素（即3），或者如果我跳第二步，那么我可以跳到第三个元素（即1）
第二个元素是3，所以我最多可以跳3次。在第一次跳转中，我可以达到1，在第二次跳转中，我可以达到0，在第三次跳转中，我可以达到4
这样，我希望以最少的跳转次数从数组的第一个元素到达最后一个元素<所以输出将是，从第一个元素2，我将跳到3。然后从3跳到4（最后一个元素）。所以跳了两次。( 2 - 3 - 4 )

#include<iostream>
#include<vector>
#include<climits>
using namespace std;

int jump(int arr[], int n, int start, vector<int> &vec)
{
    if(start == n-1)  // if start is the last element in array
       return 0;

    if( arr[start] == 0)  // if array element is 0 
       return 0;

    vector<int> vec1 = vec;
    vector<int> vec2 = vec;

    int minimum = INT_MAX;
    for( int i = 1 ; i <= arr[start]; i++ )
    {
        vec1.push_back(start);

        int _jump = 1 + jump( arr, n, start+i, vec1); // considering every jump 

        vec = (_jump < minimum) ? vec1 : vec2;

        minimum = min(minimum, _jump);
    }
        return minimum;

}

int main()
{
    int arr[] = { 2, 3, 1, 0, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);

    vector<int> vec;
    cout << "Number of jumps " << jump(arr, n, 0, vec) << endl;
    cout<<"Sequence is "<<endl;
    for( auto x : vec)
        cout << x <<" ";  
    return 0;
}          

输出

Number of jumps 2      
Sequence is      

预期产出

 Number of jumps 2       
 Sequence is 2 3 4

Answer 1

从本质上讲，这是最小的修复，因此示例数据可以正常工作。我没有检查所有的边缘情况。例如，如果无法到达终点，则可能需要打印除INT\u MAX值以外的内容。

问题1

您希望输出值（即示例中的2、3、4），而不是索引（0、1、4）。因此，您必须推送值而不是索引。

vec1.push_back(arr[start]);

问题二

if(start == n-1)  // if start is the last element in array
   return 0;

这将不会在到达结束时添加最终值。您必须添加最后一个值：

vec.push_back(arr[start]);

问题3

if( arr[start] == 0)  // if array element is 0 
   return 0;

一个没有到达终点的序列，将被认为是非常好的。您应该返回一个大值。因为_jump是一个返回值，返回值应该是INT_MAX-1，最小值也应该初始化为该值。

或者，也可以返回其他值，如n。

问题4

最后，以下条件不正确：

vec = (_jump < minimum) ? vec1 : vec2;

当条件未被验证时，需要在vec1中复制的是vect2，因为循环使用vect1。

Answer 2

下面是一个例子，它将设置一个向量，其中每个索引在访问该索引后存储序列中正确的下一步。我让您使用结果向量按照从第一个元素到结尾的顺序编码。我还纠正了这个条件if（arr[start]==0）返回"infinity"，因为如果我们访问这个元素，我们不能完成序列。

#include<iostream>
#include<vector>
#include<climits>
using namespace std;

int jump(int arr[], int n, int start, vector<int> &vec)
{
    if(start == n-1)  // if start is the last element in array
       return 0;

    if( arr[start] == 0)  // if array element is 0 
       return INT_MAX - n;

    int minimum = INT_MAX;
    int step;
    for( int i = 1 ; i <= arr[start]; i++ )
    {
        int _jump = 1 + jump( arr, n, start+i, vec); // considering every jump 

        if (_jump < minimum){
          minimum = _jump;
          step = start + i;
        }
    }

    vec.at(start) = step;

    return minimum;
}

int main()
{
    int arr[] = { 2, 3, 1, 0, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);

    vector<int> vec(n, -1);
    cout << "Number of jumps " << jump(arr, n, 0, vec) << endl;
    cout<<"Vector: "<<endl;
    for( auto x : vec)
        cout << x <<" ";  
    return 0;
}