1340. Jump Game V¶
题目信息¶
- 题号:
1340
- 难度:
Hard
- 主题:
数组、动态规划、深度优先搜索
- 原题:
- 重点:
可向左右最多
d格跳到严格更小的值;路径中间若出现大于等于当前值的元素会阻挡该方向
题目重述¶
给定整数数组 arr 和最大跳跃距离 d。从下标 i 可以向左或向右跳到距离不超过 d 的下标 j,条件是 arr[j] < arr[i],并且 i 与 j 之间所有位置的值也都严格小于 arr[i]。
可以从任意下标开始。请返回一次跳跃序列最多能够访问的下标数量,起始下标也计入。
1 <= arr.length <= 1000,1 <= arr[i] <= 10^5,1 <= d <= arr.length。
自建示例¶
严格下降序列可以逐项访问:
输入:arr = [7,6,5,4], d = 2
输出:4
解释:可以按 0 -> 1 -> 2 -> 3 跳跃,共访问四个位置。
相等高度不能作为目标也会阻挡:
输入:arr = [3,3], d = 1
输出:1
解释:任一位置都不能跳到另一个相等值位置。