2024.2.5力扣每日一题——跳跃游戏6

题目来源

力扣每日一题；题序：1696

我的题解

方法一 深度搜索实现

使用深度搜索，每次选择一个在范围内的跳跃点，但是时间通不过。

时间复杂度：O($n^2$)
空间复杂度：O(n)

int res=0;
public int maxResult(int[] nums, int k) {
    int sum=nums[0];
    for(int i=1;i<=k&&i<nums.length;i++){
        dfs(nums,k,sum+nums[i],i);
    }
    return res;
}
public void dfs(int[] nums, int k,int sum,int index){
    if(index>=nums.length)
        return ;
    if(index==nums.length-1){
        res=Math.max(res,sum);
        return ;
    }
    for(int i=1;i<=k&&index+i<nums.length;i++){
        dfs(nums,k,sum+nums[i+index],i+index);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

方法二 动态规划+双端队列

每一个位置的最大值取决于前面 k 步的最大得分，再加上当前位置的得分，由此想到可以使用动态规划来解决这个问题。
用 dp[i] 来表示到达位置 i 的最大得分。初始状态 dp[0]=nums[0]，表示位置 0 的得分是它本身的得分。状态转移方程是
dp [ i ] = max ⁡ max ⁡ ( 0 , i − k ) ≤ j < i { dp [ j ] } + nums [ i ] \textit{dp}[i] = \max_{\max(0, i-k) \leq j < i} \{ \textit{dp}[j] \} + \textit{nums}[i] dp[i]=maxmax(0,i−k)≤j<i​{dp[j]}+nums[i]
其中 max⁡(0,i−k)≤j<i。
其中前 k 步的最大值，使用双端队列可以达到 O(n) 的时间复杂度。

时间复杂度：O(n)
空间复杂度：O(n)

public int maxResult(int[] nums, int k) {
    int n=nums.length;
    Deque<Integer> queue=new LinkedList<>();
    queue.offerLast(0);
    int[] dp=new int[n];
    dp[0]=nums[0];
    for(int i=1;i<n;i++){
    	//删除过期的索引位置
       while(queue.peekFirst()<i-k){
        queue.pollFirst();
       }
       //更新  前一个范围内的最大值+当前值
       dp[i]=dp[queue.peekFirst()]+nums[i];
       // 删除比选择位置小的
       while(!queue.isEmpty()&&dp[queue.peekLast()]<=dp[i]){
        queue.pollLast();
       }
       queue.offerLast(i);
    }
    return dp[n-1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈