题目描述

小红有一个长度为n的数组a，他想从里面选一些数拿走使 得这些数求和结果最大。但小红受一些限制。

题解

题意可以大致抽象为，给定一个大小为 $n$ 的序列，从起点 $0$ 开始跳，每次最多向右跳 $k$ 个位置，求到达序列最右端点时所经过所有点的权值之和最大为多少？

不过值得注意的是，这里的最右端点在本题中不一定选，所以我们可以建立一个虚拟的第 $n + 1$ 个点作为序列右端点，且该点的权值为 $0$ 。

首先考虑经典的 DP ，定义 $dp[i]$ 为，考虑了前 $i$ 个数，且最后一个选择的数为 $i$ 的最大值。

转移方程为 : $dp[i] = max(dp[i - j] + nums[i], dp[i])$，其中 $j \in [1, k]$，此时的复杂度为 $O(nk)$ 并不能满足题目的要求。