题目描述

小明和朋友们一起玩跳格子游戏，每个格子上有特定的分数score[] =[1 -1-6 7 -17 7]，从起点score[0开始，每次最大的步长为k，请你返回小明跳到终点score[n-1]时，能得到的最大得分。

思路:单调队列优化的动态规划

根据题目意思，我们可以想到一种很简单的动态规划方法：从左到右dp，对于每一个i , 去看$[i-k,i-1]$ 这个下标范围内的最大可能的$dp$值，假设是$x$ , 那么就是$dp[i] = x + a[i]$

这样复杂度是$O(nk)$的不能拿满分，所以先学习一下下面两个算法:

先学习一下单调队列

在学习下单调队列优化动态规划