当前位置:网站首页>LeetCode 1696. 跳跃游戏 VI 每日一题
LeetCode 1696. 跳跃游戏 VI 每日一题
2022-07-07 15:32:00 【@小红花】
问题描述
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一开始你在下标 0 处。每一步,你最多可以往前跳 k 步,但你不能跳出数组的边界。也就是说,你可以从下标 i 跳到 [i + 1, min(n - 1, i + k)] 包含 两个端点的任意位置。
你的目标是到达数组最后一个位置(下标为 n - 1 ),你的 得分 为经过的所有数字之和。
请你返回你能得到的 最大得分 。
示例 1:
输入:nums = [1,-1,-2,4,-7,3], k = 2
输出:7
解释:你可以选择子序列 [1,-1,4,3] (上面加粗的数字),和为 7 。
示例 2:输入:nums = [10,-5,-2,4,0,3], k = 3
输出:17
解释:你可以选择子序列 [10,4,3] (上面加粗数字),和为 17 。
示例 3:输入:nums = [1,-5,-20,4,-1,3,-6,-3], k = 2
输出:0
提示:
1 <= nums.length, k <= 105
-104 <= nums[i] <= 104来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/jump-game-vi
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
java
class Solution {
public int maxResult(int[] nums, int k) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp,Integer.MIN_VALUE);
dp[0] = nums[0];
for(int i = 0;i < n;i++){
//跳k次
for(int j = i + 1;j < n && j <= i + k;j++){
//跳跃后的分数
int nextScore = dp[i] + nums[j];
//更新为跳跃后更高的分数
if(nextScore > dp[j]) dp[j] = nextScore;
//过滤
if(dp[j] >= dp[i]) break;
}
}
return dp[n - 1];
}
}
边栏推荐
- Three. JS series (1): API structure diagram-1
- 【Vulnhub靶场】THALES:1
- dapp丨defi丨nft丨lp单双币流动性挖矿系统开发详细说明及源码
- 【PHP】PHP接口继承及接口多继承原理与实现方法
- 3000 words speak through HTTP cache
- laravel构造函数和中间件执行顺序问题
- Opportunity interview experience summary
- 如何快速检查钢网开口面积比是否符合 IPC7525
- Read PG in data warehouse in one article_ stat
- Spark Tuning (III): persistence reduces secondary queries
猜你喜欢
面向接口编程
【Android -- 数据存储】使用 SQLite 存储数据
【DesignMode】代理模式(proxy pattern)
爬虫(17) - 面试(2) | 爬虫面试题库
如何快速检查钢网开口面积比是否符合 IPC7525
3000 words speak through HTTP cache
Talk about the realization of authority control and transaction record function of SAP system
As an Android Developer programmer, Android advanced interview
Module VI
Vs2019 configuration matrix library eigen
随机推荐
Build an all in one application development platform, light flow, and establish a code free industry benchmark
字节跳动Android金三银四解析,android面试题app
Pycharm terminal enables virtual environment
使用JSON.stringify()去实现深拷贝,要小心哦,可能有巨坑
【DesignMode】外观模式 (facade patterns)
three. JS create cool snow effect
一文读懂数仓中的pg_stat
掌握这套精编Android高级面试题解析,oppoAndroid面试题
os、sys、random标准库主要功能
Three. JS series (1): API structure diagram-1
C语言进阶——函数指针
射线与OBB相交检测
node:504报错
Have fun | latest progress of "spacecraft program" activities
Laravel post shows an exception when submitting data
掌握这个提升路径,面试资料分享
Ray and OBB intersection detection
JS 模块化
Find tags in prefab in unity editing mode
Master this promotion path and share interview materials