1696. Jump Game VI
- 2 minutes read - 546 words題目
You are given a 0-indexed integer array nums and an integer k.
You are initially standing at index 0. In one move, you can jump at most k steps forward without going outside the boundaries of the array. That is, you can jump from index i to any index in the range [i + 1, min(n - 1, i + k)] inclusive.
You want to reach the last index of the array (index n - 1). Your score is the sum of all nums[j] for each index j you visited in the array.
Return the maximum score you can get.
想法
這題很容易想到一個 O(n*k) 的 DP 解法,但那樣會 TLE。
所以,我們要對 DP 更新的方式做一些改變。
我們多拿一個陣列當成 deque 來儲存位置需要處裡的位置。
這個 deque 有個特色,就是他是單調嚴格遞增的。
遍歷的時候,先把其中已經不在可抵達範圍內的拿掉。
該位置的 DP 值就會是 deque 最前面位置的最大分數加上該位置的分數。
你可能會想說,為什麼最前面位置的最大分數會最佳呢?
因為我們還會移除所有雖然在範圍內,但最大分數較該位置最大分數小的位置。
遍歷完就可以得到完整的 DP 陣列了,複雜度應該是 O(n)。
實作
Javascript
var maxResult = function (nums, k) {
const n = nums.length;
// dp 陣列用來存到 i 處最大分數
let dp = new Array(n);
// deque 用來存候選位置
let deque = [];
// 初始化,分別放入 i = 0 的值與位置
dp[0] = nums[0];
deque.push(0);
// 遍歷 nums
for (let i = 1; i < n; i++) {
// 如果 deque 最前面那個超過可到達範圍,把它移除
if (deque.length && deque[0] < i - k) deque.shift();
// i 位置的最大分數會是 deque 中離 i 最遠的最大分數加上 i 位置的分數
dp[i] = dp[deque[0]] + nums[i];
// 把 deque 中位置的最大分數比 i 位置的最大分數小的位置移除
while (deque.length && dp[i] >= dp[deque[deque.length - 1]]) deque.pop();
// 把 i 位置放入 deque
deque.push(i);
}
// 回傳到最後一個位置的最大分數
return dp[n - 1];
};