路径、树形与对抗状态

def first_player_wins(nums: list[int]) -> bool:
    """Players take from either end in turn; does the first end with at least as much? (LC 486)"""
    n = len(nums)
    dp = nums[:]  # dp[j] for the current i: best (mover - opponent) on nums[i..j]; i == j: take it
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            dp[j] = max(nums[i] - dp[j], nums[j] - dp[j - 1])  # take the left end, or the right
    return dp[n - 1] >= 0

// Players take from either end in turn; does the first end with at least as much? (LC 486)
bool firstPlayerWins(const vector<int>& nums) {
    int n = nums.size();
    vector<int> dp = nums;  // dp[j] for the current i: best (mover - opponent) on nums[i..j]; i == j: take it
    for (int i = n - 2; i >= 0; i--)
        for (int j = i + 1; j < n; j++)
            dp[j] = max(nums[i] - dp[j], nums[j] - dp[j - 1]);  // take the left end, or the right
    return dp[n - 1] >= 0;
}

class Solution {
    // Players take from either end in turn; does the first end with at least as much? (LC 486)
    boolean firstPlayerWins(int[] nums) {
        int n = nums.length;
        int[] dp = nums.clone(); // dp[j] for the current i: best (mover - opponent) on nums[i..j]; i == j: take it
        for (int i = n - 2; i >= 0; i--)
            for (int j = i + 1; j < n; j++)
                dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j - 1]); // take the left end, or the right
        return dp[n - 1] >= 0;
    }
}

// firstPlayerWins: players take from either end in turn; does the first end with at least as much? (LC 486)
func firstPlayerWins(nums []int) bool {
	n := len(nums)
	dp := append([]int(nil), nums...) // dp[j] for the current i: best (mover - opponent) on nums[i..j]
	for i := n - 2; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			dp[j] = max(nums[i]-dp[j], nums[j]-dp[j-1]) // take the left end, or the right
		}
	}
	return dp[n-1] >= 0
}

from collections import deque


def max_jump_score(nums: list[int], k: int) -> int:
    """From index 0 to n - 1 in jumps of 1..k steps: the best sum of the values landed on (LC 1696)."""
    n = len(nums)
    dp = [0] * n  # dp[i]: best score landing on i
    dp[0] = nums[0]
    dq = deque([0])  # indexes in the last k, dp decreasing: the front is the best place to jump from
    for i in range(1, n):
        if dq[0] < i - k:
            dq.popleft()  # too far back to reach i
        dp[i] = dp[dq[0]] + nums[i]
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()  # i is closer and no worse: they will never be the best again
        dq.append(i)
    return dp[-1]

// From index 0 to n - 1 in jumps of 1..k steps: the best sum of the values landed on (LC 1696).
long long maxJumpScore(const vector<int>& nums, int k) {
    int n = nums.size();
    vector<long long> dp(n);  // dp[i]: best score landing on i
    dp[0] = nums[0];
    deque<int> dq{0};  // indexes in the last k, dp decreasing: the front is the best place to jump from
    for (int i = 1; i < n; i++) {
        if (dq.front() < i - k) dq.pop_front();  // too far back to reach i
        dp[i] = dp[dq.front()] + nums[i];
        while (!dq.empty() && dp[dq.back()] <= dp[i]) dq.pop_back();  // i is closer and no worse
        dq.push_back(i);
    }
    return dp[n - 1];
}

class Solution {
    // From index 0 to n - 1 in jumps of 1..k steps: the best sum of the values landed on (LC 1696).
    long maxJumpScore(int[] nums, int k) {
        int n = nums.length;
        long[] dp = new long[n]; // dp[i]: best score landing on i
        dp[0] = nums[0];
        Deque<Integer> dq = new ArrayDeque<>(List.of(0)); // indexes in the last k, dp decreasing
        for (int i = 1; i < n; i++) {
            if (dq.peekFirst() < i - k) dq.pollFirst(); // too far back to reach i
            dp[i] = dp[dq.peekFirst()] + nums[i];
            while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) dq.pollLast(); // i is closer and no worse
            dq.offerLast(i);
        }
        return dp[n - 1];
    }
}

// maxJumpScore: from index 0 to n - 1 in jumps of 1..k steps, the best sum of the values landed on (LC 1696).
func maxJumpScore(nums []int, k int) int {
	n := len(nums)
	dp := make([]int, n) // dp[i]: best score landing on i
	dp[0] = nums[0]
	dq := []int{0} // indexes in the last k, dp decreasing: the front is the best place to jump from
	for i := 1; i < n; i++ {
		if dq[0] < i-k {
			dq = dq[1:] // too far back to reach i
		}
		dp[i] = dp[dq[0]] + nums[i]
		for len(dq) > 0 && dp[dq[len(dq)-1]] <= dp[i] {
			dq = dq[:len(dq)-1] // i is closer and no worse
		}
		dq = append(dq, i)
	}
	return dp[n-1]
}