给定一个非负整数数组，表示最大数量可以从该元素向前迈出的步骤。指针最初位于数组的第一个索引 [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#includeint 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 输出
Enter size of array : 7Enter elements in the array :2 1 1 5 2 1 1Minimum number of steps : 3
登录后复制
以上就是C程序寻找到达末尾的最小跳数的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2587259.html
