算法动态规划 ⑦ ( LeetCode 55. 跳跃游戏 | 算法 | 代码展示 )
一、跳跃游戏
LeetCode 55. 跳跃游戏 : https://leetcode.cn/problems/jump-game/
给定一个 非负整数数组 nums ,你最初位于数组的 第一个下标 0 位置 。
数组中的每个元素 代表你在该位置可以 跳跃的最大长度。
判断你 是否能够到达最后一个下标。
二、算法分析
给定一个一维数组 , 数组元素不能有负数 , 如 : {2, 2, 0 , 1} ;
开始时 , 处于 第 0 个元素 2 位置 , 则说明 最多可以向右跳 2 步 , 其可以跳 0 步 , 1 步 , 2 步 ;
- 如果从 第 0 个元素 向右跳 2 步 , 跳到的 第 2 个元素 0 位置 , 则在第 2 个元素位置 最多只能向右跳 0 步 , 永远无法跳到终点 ;
- 如果从 第 0 个元素 向右跳 0 步 , 原地不动 , 没有任何意义 ;
因此 , 这里 选择向右跳 1 步 , 跳到 第 1 个元素 2 位置 ;
从 第 1 个元素 2 位置 可以选择向右 跳 0 步 , 1 步 , 2 步 ;
- 选择跳 0 步 没有意义 ;
- 选择跳 1 步 到达 第 2 个元素 0 位置 , 永远无法到达终点 ;
- 选择跳 2 步 , 可以到达终点 ;
该问题可以使用 动态规划 算法 进行解决 ;
① 可行性 : 上述问题 , 最终问的是 可行性 , 也就是方案数 大于 0 即可 ;
② 方向性 : 一维数组元素都是大于等于 0 的 , 从左到右跳跃 , 有方向性 ;
③ 一维数组 : 问题是基于一维数组的 , 是变换下标的问题 , 符合 坐标型动态规划 中的一维坐标动态规划 ;
三、代码示例
代码示例 :
class Solution {
public boolean canJump(int[] array) {
// 验证函数参数
if (array == null || array.length == 0) {
return false;
}
// 1. 动态规划状态 State
// dp[i] 表示 从 0 位置出发能否跳到 i 位置
boolean[] dp = new boolean[array.length];
// 2. 动态规划初始化 Initialize
// 跳跃游戏初始位置就是 0 位置 , 该位置肯定能跳到
dp[0] = true;
// 3. 动态规划方程 Function
// dp[i] 表示的 i 位置是否可达, 依赖于 小于 i 的 j 位置
// 在 j 位置可达的前提下
// 从 j 开始进行跳跃 , 可以跳转到 i 或者越过 i 则表示 i 点可达
for (int i = 0; i < array.length; i ) {
for (int j = 0; j < i; j ) {
// dp[j] 表示 j 位置是否可达
// j array[j] 表示 从 j 位置开始跳跃 , 最多跳跃 array[j] , 看是否大于等于 i
// 这里判定大于等于 是因为 可以不用跳跃 array[j] 那么多
// 0 ~ array[j] 中肯定有正好等于 i 的数值
if (dp[j] && j array[j] >= i) {
dp[i] = true;
break;
}
}
}
// 4. 动态规划答案 Answer
return dp[array.length - 1];
}
public static void main(String[] args) {
int[] array = {2, 2, 0 , 1};
boolean result = new Solution().canJump(array);
System.out.println("最终能否达到终点 : " result);
}
}
执行结果 :
最终能否达到终点 : true
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggbice
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01