计算跳转到C ++末尾的方式数量
给定一个正数数组。每个元素代表从该索引可以到达数组末尾的最大跳转数。目的是找到从该元素可以到达终点的跳跃次数。如果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（intarr[]，intsize）接受一个数组，并返回跳转到末尾的方式数的计数。
使用数组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