🔗 🟡 2786. Visit Array Positions to Maximize Score 1733

tags: `Biweekly Contest 109` `動態規劃(DP)`

題意

給定一個下標從 $0$ 開始的整數陣列 $nums$ 和一個正整數 $x$ 。

你一開始在陣列的 $0$ 號位置，可以根據以下規則到其他位置：

如果你現在在 $i$ 號位置，可以移動到任何滿足 $i < j$ 的位置 $j$ 。
對於你到達的每個位置 $i$ ，你可以獲得分數 $nums[i]$ 。
如果你從位置 $i$ 移動到位置 $j$ ，但 $nums[i]$ 和 $nums[j]$ 的奇偶性不同，那麼你將失去分數 $x$ 。

你可以移動到任何 $j$ 號位置,只要 $i < j$ 。

返回能夠獲得的最大總分。

請注意，一開始你有 $nums[0]$ 分。

約束條件

$2 \leq nums.length \leq 10^5$
$1 \leq nums[i], x \leq 10^6$

思路：動態規劃(DP)

寫法一

令 $dp[i][p]$ 表示考慮到第 $i$ 個位置，最後一個位置的奇偶性為 $p$ (0 表示偶數，1 表示奇數) 時，能獲得的最大分數。

當從位置 $i-1$ 到達位置 $i$ 時，我們有兩個選擇：

如果 $nums[i-1]$ 和 $nums[i]$ 的奇偶性相同 ( $p$ 相同)，由於 $nums[i]$ 為正整數，選擇走到位置 $i$ 會使分數增加，因此 $dp[i][p]$ 可以從 $dp[i-1][p] + nums[i]$ 獲得。
如果奇偶性不同，則 $dp[i][p]$ 可以從 $dp[i-1][1-p] + nums[i] - x$ 獲得，其中 $1-p$ 表示與 $p$ 相反的奇偶性。

故可以得到狀態轉移方程：

$dp[i][p] = \max(dp[i-1][p] + nums[i], dp[i-1][1-p] + nums[i] - x)$
$dp[i][1-p] = dp[i-1][1-p]$ ，表示當前位置的另一種奇偶性的最大得分不變。

具體做法如下：

初始化 $dp$ $d p$ 陣列， $dp[i][p]$ $d p [i] [p]$ 表示考慮到第 $i$ $i$ 個位置，最後一個位置的奇偶性為 $p$ $p$ 時，能獲得的最大分數。
- 由於從位置 $0$ 開始，所以 $dp[0][nums[0] \bmod 2] = nums[0]$ 。
- $dp$ 陣列的其他值初始化為負無窮，表示未達到該位置。
- 初始化 $\text{ans} = nums[0]$ 。
遍歷從 $1$ 到 $n-1$ 的位置 $i$ 。對於每個 $i$ ，根據 $nums[i]$ 的奇偶性 $p = nums[i] \bmod 2$ 更新 $dp[i][p]$ 和 $dp[i][1-p]$ 。
每一步都更新最大分數 $ans$ 為 $\max(\text{ans}, dp[i][p])$ 。
最後返回 $ans$ 即可。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，其中 $n$ 是陣列 $nums$ 的長度，只需要遍歷一次陣列。
空間複雜度： $\mathcal{O}(n)$ ，使用了長度為 $n \times 2$ 的二維陣列 $dp$ 。

class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        n = len(nums)
        ans = nums[0]
        dp = [[float('-inf'), float('-inf')] for _ in range(n)]
        dp[0][nums[0] % 2] = nums[0]
        for i in range(1, n):
            p = nums[i] % 2 # parity, 0: even, 1: odd
            dp[i][p] = max(dp[i - 1][p] + nums[i], dp[i - 1][1 - p] + nums[i] - x)
            dp[i][1 - p] = dp[i - 1][1 - p]
            ans = max(ans, dp[i][p])
        return ans

const int INF = 0x3f3f3f3f;
class Solution {
public:
    long long maxScore(vector<int>& nums, int x) {
        int n = nums.size();
        long long ans = nums[0];
        vector<vector<long long>> dp(n, vector<long long>(2, -INF));
        dp[0][nums[0] % 2] = nums[0];
        for (int i = 1; i < n; i++) {
            int p = nums[i] % 2;
            dp[i][p] = max(dp[i - 1][p] + nums[i], dp[i - 1][1 - p] + nums[i] - x);
            dp[i][1 - p] = dp[i - 1][1 - p];
            ans = max(ans, dp[i][p]);
        }
        return ans;
    }
};

寫法二：空間優化

注意到在寫法一中， $dp[i][p]$ 的值只和前一個狀態的 $dp[i-1][p]$ 和 $dp[i-1][1-p]$ 有關，且 $dp[i][1-p]$ 的值在每一步都不變，因此可以對空間進行優化，只使用一個長度為 $2$ 的陣列 $f$ 來存儲 $dp[i][p]$ 和 $dp[i][1-p]$ 的值。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，其中 $n$ 是陣列 $nums$ 的長度，只需要遍歷一次陣列。
空間複雜度： $\mathcal{O}(1)$ ，只使用了長度為 $2$ 的陣列 $f$ 。

class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        n = len(nums)
        ans = nums[0]
        f = [float('-inf'), float('-inf')]
        f[nums[0] % 2] = nums[0]
        for i in range(1, n):
            p = nums[i] % 2 # parity, 0: even, 1: odd
            f[p] = max(f[p] + nums[i], f[1 - p] + nums[i] - x)
            ans = max(ans, f[p])
        return ans

const int INF = 0x3f3f3f3f;
class Solution {
public:
    long long maxScore(vector<int>& nums, int x) {
        int n = nums.size();
        long long ans = nums[0];
        vector<long long> dp(2, -INF);
        dp[nums[0] % 2] = nums[0];
        for (int i = 1; i < n; i++) {
            int p = nums[i] % 2;
            dp[p] = max(dp[p] + nums[i], dp[1 - p] + nums[i] - x);
            ans = max(ans, dp[p]);
        }
        return ans;
    }
};