题目描述
科科最近在修炼魔法，一日他来到魔法城堡，城堡里有一个长长的台阶,而台阶的最终点便是魔法奥秘。
这是一个魔力台阶，每个台阶都有一个魔力值，魔力值代表下一步科科最大可以跨越的台阶数。科科当前处在第1级台阶上，但是科科的体力有限，最多只能跨越K次。科科现在拜托你帮他计算下他能否拿到魔法奥秘。
如果能够拿到返回最少跨越的次数，拿不到则返回-1。
输入
台阶长度n (1<=n<=10^5)
台阶魔力值，[M1, M2… Mn]由一个长度为n的数组表示，代表1~n级台阶的魔力值。(0<=Mi<=10^5)
最大的跨越次数K(1<=k<=10^5)
输出
输出一个整数，拿到魔法奥秘最少需要跨越的次数，如果拿不到，返回-1
【分析】
这道题与力扣的 45. 跳跃游戏 II 类似，但不完全相同，本题存在拿不到的情况。
我们走到某一台阶时，必是从之前的一级台阶过来的，且当前台阶的最小步数是之前台阶的最小步数 +1 ，则容易想到本题应用动态规划。
构建一个一维数组 dp，长度为 n ，其中 dp[i] 代表从第一级台阶走到当前台阶的最小步数，所以有：
1.dp[0]=0，初始时即在该位置；
2.然后将其余位置置为无穷大， 表示初始时还不能走到当前位置。
我们只需在每个台阶可走的步数中进行遍历，将能达到的位置均置为最小值即可
【实现】
let n; // 台阶长度
let array = []; // 台阶魔力值
let k; //最大跨越次数
const dp = new Array(n).fill(Infinity); // 构建dp数组，初始值为无穷大
dp[0] = 0; // 第一级台阶置0
// 开始遍历，只到倒数第二级台阶
for (let i = 0; i < n - 1; i++) {
// 获取每一级台阶上的魔力值，向后走其所有的可能情况，实时更新数组
for (let j = 1; j <= array[i]; j++) {
if (i + j >= n) break; // 从当前位置已走出台阶，不考虑
dp[i + j] = Math.min(dp[i + j], dp[i] + 1); // 当前位置走到新位置时，判定是否是新位置的最小步数
}
}
const res = dp[n - 1] > k ? -1 : dp[n - 1]; // 判断到达台阶终点要走的最小步数是否符合要求
console.log(res);
