74.青蛙跳格子问题
题目:青蛙跳格子问题
青蛙跳一跳，前方一百个格子如一百个数组，数组中内容有正值和负值（为青蛙跳到此处时体力增加还是减少），每次可以跳多个格子，每跳一格消耗一个体力， 问题 1：请问青蛙可以跳到一百的格子的终点吗，怎么实现的算法。 问题 2：假如青蛙每次跳过的格子为（消耗的体力为青蛙跳的格子的平方），请问可以跳到多远的距离
解题思路
能否跳到终点？
DETAILS
function canReachEnd(arr) {
const n = arr.length;
if (n === 0) return false;
// 初始化动态规划数组，dp[i] 表示到达位置 i 时的最大剩余体力
const dp = new Array(n).fill(-Infinity);
dp[0] = arr[0]; // 初始体力为第一个格子的值
for (let i = 0; i < n; i++) {
if (dp[i] === -Infinity) continue; // 当前格子不可达
for (let j = i + 1; j < n; j++) {
const k = j - i; // 跳跃步数
if (dp[i] >= k) {
// 剩余体力足够跳跃
const newEnergy = dp[i] - k + arr[j];
if (newEnergy > dp[j]) {
dp[j] = newEnergy; // 更新最大剩余体力
}
}=
}
}
return dp[n - 1] !== -Infinity; // 终点是否可达
}
// 示例输入
const exampleArr = [2, -1, 3, -5, 10];
// 问题1测试
console.log(canReachEnd(exampleArr)); // 输出: true