给定一个正数数组。每个元素代表从该索引可以到达数组末尾的最大跳转数。目的是找到从该元素可以到达终点的跳跃次数。如果arr []为[1,2,3]，则1跳可以为1，2跳可以为1或2，3跳可以为1、2或3。
例如
arr[] = {1,2,3}输出结果跳到终点的方式数： 1 1 0
For 1 we have jumps : 1, For 2 we have jumps 1 or 2, to reach the end we need just one jump of 1. For 3 we have jumps 1,2 or 3, as at its end we need no jumps.
arr[] = {4,3,6,2}输出结果跳到终点的方式数： 4 2 1 0
For 4 we have jumps : 1, 2, 3 or 4. To reach the end we need only 1,2 or 3. Ways will be 4−3−6−2, 4−6−2, 4−2, 4−3−2. Total 4. For 3 we have jumps 1, 2 or 3 to reach the end we need both. Ways will be 3−6−2, 3−2. Total 2. For 6 we have jumps 1 to 5, to reach the end we need 1. Ways will be 6−2. Total 1. For 2 we have jumps 1or 2, as at its end we need no jumps.
以下程序中使用的方法如下-
在这种方法中，对于每个元素arr [i]，我们将为到达arr [i]且可从当前元素到达的所有元素添加到达数组末尾的方式计数。如果我们可以在一个跳转中直接从arr [i]到达结尾，则在此计数上加1作为arr [i]的方式。
取一个整数数组arr []。
函数reach_end（int arr []，int size）接受一个数组，并返回跳转到末尾的方式数的计数。
使用数组arr_2 []来存储从arr []的每个元素到达末尾的方式。
使用memset（arr_2，0，sizeof(arr_2)）用0初始化整个arr_2 []。
使用for循环从i = size-2到i = 0遍历arr []，因为不会考虑最后一个元素。
取temp = size − i −1。如果temp> = arr [i]，则可以一次跳转直接到达结尾。增量方式使用arr_2 [i] ++计算arr [i]。
现在，对于所有其他可以到达终点并且可以从arr [i]到达的元素，向arr_2 [i]添加方法数量。
对于上述遍历，使用从j = i + 1到j <size-1和j <= arr [i] + i的for循环。如果任何arr [j]不为-1，则将其添加到arr_2 [i]。
如果arr_2 [i]仍为0，则将其设置为-1，这意味着它无法结束。
在所有循环的结尾，我们将使arr_2 []能够到达arr []的每个元素的结尾。
使用for循环将arr_2打印为结果。
#include <bits/stdc++.h>
using namespace std;
void reach_end(int arr[], int size){
int arr_2[size];
memset(arr_2, 0, sizeof(arr_2));
for (int i = size−2; i >= 0; i−−){
int temp = size − i − 1;
if (arr[i] >= temp){
arr_2[i]++;
}
for (int j = i+1; j < size−1 && j <= arr[i] + i; j++){
if (arr_2[j] != −1){
arr_2[i] = arr_2[i] + arr_2[j];
}
}
if(arr_2[i] == 0){
arr_2[i] = −1;
}
}
cout<<"跳到终点的方式数： ";
for (int i=0; i < size; i++){
cout<<arr_2[i] << " ";
}
}
int main(){
int arr[] = {2, 3, 7, 1, 8, 9};
int size = sizeof(arr) / sizeof(arr[0]);
reach_end(arr, size);
return 0;
}输出结果如果我们运行上面的代码，它将生成以下输出-
跳到终点的方式数： 8 5 3 1 1 0