到达终点的最小跳数的C程序
我们得到了一个非负整数数组，该整数表示可以从该元素进行的最大步数。指针最初位于数组的第一个索引[0 index]处。您的目标是以最少的步骤数达到数组的最后一个索引。如果无法到达数组的末尾，则打印最大整数。
天真的方法是从初始{primary}组件开始，然后递归地调用可从第一个元素访问的所有组件。使用从第一个可访问元素开始到达结尾所需的最小跳转范围，计算从第一个到达结尾的最小跳转范围。
minJumps(start, end) = Min ( minJumps(k, end) )for all k accessible from the start
在这里，我们将使用自顶向下的动态编程方法。我们将使用Hashmap来存储子问题的结果，并且每当创建解决方案时，首先要检查子问题是否已经解决，如果是，则使用它。
Input: { 1, 2, 4, 1, 2, 2, 1, 1, 3, 8 }Output: Minimum number of steps = 6 {1-->2-->4-->1-->3-->8}
说明
第一个元素为1，因此只能转到2。第二个元素为2，因此最多可以进行2步，例如到4或1。从达到1的位置开始到4，依此类推。
查找到达数组末尾的最小跳转次数的动态编程方法的复杂度为O（n ^ 2），空间复杂度为O(n)
示例
#include<stdio.h>#include<limits.h>
int min_steps (int arr[], int n){
int steps[n];
int i, j;
if (n == 0 || arr[0] == 0)
return INT_MAX;
steps[0] = 0;
for (i = 1; i < n; i++){
steps[i] = INT_MAX;
for (j = 0; j < i; j++){
if (i <= j + arr[j] && steps[j] != INT_MAX){
steps[i] = (steps[i] < (steps[j] + 1)) ? steps[i] : steps[j] + 1;
break;
}
}
}
return steps[n - 1];
}
int main (){
int arr[100];
int n;
printf ("输入数组的大小：");
scanf ("%d", &n);
printf ("在数组中输入元素：");
for (int i = 0; i < n; i++){
scanf ("%d", &arr[i]);
}
printf ("Minimum number of steps : %d", min_steps (arr, n));
return 0;
}
输出结果
Enter size of array : 7Enter elements in the array :2 1 1 5 2 1 1
Minimum number of steps : 3
以上是 到达终点的最小跳数的C程序 的全部内容， 来源链接： utcz.com/z/348910.html
