网站建站公司广州,南京江北新区楼盘,番禺建网站公司,wordpress 段落 两格文章目录 题目描述问题分析程序代码 题目描述
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一开始你在下标 0 处。每一步#xff0c;你最多可以往前跳 k 步#xff0c;但你不能跳出数组的边界。也就是说#xff0c;你可以从下标 i 跳到 [i 1#xff0c; min(… 文章目录 题目描述问题分析程序代码 题目描述
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一开始你在下标 0 处。每一步你最多可以往前跳 k 步但你不能跳出数组的边界。也就是说你可以从下标 i 跳到 [i 1 min(n - 1, i k)] 包含 两个端点的任意位置。
你的目标是到达数组最后一个位置下标为 n - 1 你的 得分 为经过的所有数字之和。
请你返回你能得到的 最大得分 。
问题分析
状态表示dp[i]表示到达位置 i 的最大得分
初始状态dp[0] nums[0]
状态计算dp[i] max{dp[j]}其中max(0,i−k) j i
其中前 k 步的最大值可以用一个双端队列进行维护。
程序代码
func maxResult(nums []int, k int) int {n : len(nums)dp : make([]int, n)dp[0] nums[0]// 双端队列q : make([]int, n)qi, qj : 0, 1for i : 1; i n; i {// 容量超了for qi qj q[qi] i - k {qi}dp[i] dp[q[qi]] nums[i]// 比你年轻能力还比你强for qi qj dp[q[qj - 1]] dp[i] {qj--}q[qj] iqj}return dp[n-1]
}
