动态规划——leetcode55、跳跃游戏
2022/8/24 23:26:34
本文主要是介绍动态规划——leetcode55、跳跃游戏,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述:
解题方法:动态规划
动态规划解题步骤:
确定状态:
-
- 最后一步:如果能跳到最后一个下标,我们考虑他的最后一步到n-1(最后一个下标),这一步是从 i 跳过来的,i<n-1;
这需要满足两个条件:
- 可以跳到 i ;
- 最后一步跳跃的距离 <= 从i可以跳跃的最大距离,即 n-1-i <= nums[i]
-
- 子问题:我们需要知道能不能跳到i
状态:设f[j]能不能跳到石头j
转移方程:
初始条件和边界情况:
初始条件:f[0] = True,因为一开始就在0位置
计算顺序:
计算:f[1],f[2],...,f[n-1]
时间复杂度:O(n2),空间复杂度(数组大小):O(n)
代码:
public boolean canJump(int[] nums) { int n = nums.length; boolean[] f = new boolean[n]; f[0] = true; for(int j = 1; j < n; j++){ f[j] = false; for(int i = 0; i < j; i++){ if(f[i] && i + nums[i] >= j){ f[j] = true; break; } } } return f[n-1]; }
这篇关于动态规划——leetcode55、跳跃游戏的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享