C程序寻找到达末尾的最小跳数

2023年 8月 28日 45.3k 0

C程序寻找到达末尾的最小跳数

给定一个非负整数数组,表示最大数量
可以从该元素向前迈出的步骤。指针最初位于数组的第一个索引 [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

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论