给定一个非负整数数组，表示最大数量 可以从该元素向前迈出的步骤。指针最初位于数组的第一个索引 [0 索引] 处。你的目标是到达最后 最少步数中数组的索引。如果无法到达 数组末尾，然后打印最大整数。
天真的方法是从初始{主要}组件开始，并递归调用可从第一个元素访问的所有组件。从第一个到达末尾的最小跳转范围是使用从第一个可访问的元素到达末尾所需的最小跳转范围来计算的。
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#include 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 ("Enter size of the array:"); scanf ("%d", &n); printf ("Enter elements in the array:"); 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 : 7 Enter elements in the array :2 1 1 5 2 1 1 Minimum number of steps : 3
