Every day a Leetcode

題目來源：3259. 超級(jí)飲料的最大強(qiáng)化能量

解法1：記憶化搜索

本題的狀態(tài)定義 dfs(i,j)。其中 j=0,1，分別表示最后選的是 energyDrinkA[i] 還是 energyDrinkB[i]。

為方便實(shí)現(xiàn)，把 energyDrinkA 和 energyDrinkB 加到一個(gè)長(zhǎng)為 2 的二維數(shù)組 c 中。

分類討論：

• 繼續(xù)選 c[j] 中的元素，那么下一個(gè)數(shù)選 c[j][i?1]，需要解決的問題為：從下標(biāo) [0,i?1] 中選數(shù)字，且最后選的是 c[j] 中的元素的情況下，所選元素之和的最大值，即 dfs(i?1,j)。

• 改成選 c[j⊕1] 中的元素，那么下一個(gè)數(shù)選 c[j⊕1][i?2]，需要解決的問題為：從下標(biāo) [0,i?2] 中選數(shù)字，且最后選的是 c[j⊕1] 中的元素的情況下，所選元素之和的最大值，即 dfs(i?2,j⊕1)。其中 ⊕ 為異或運(yùn)算，通過異或 1，可以把 0 變成 1，把 1 變成 0。

代碼：

#
# @lc app=leetcode.cn id=3259 lang=python3
#
# [3259] 超級(jí)飲料的最大強(qiáng)化能量
## @lc code=start
class Solution:def maxEnergyBoost(self, energyDrinkA: List[int], energyDrinkB: List[int]) -> int:n = len(energyDrinkA)energyDrink = (energyDrinkA, energyDrinkB)@cache  # 緩存裝飾器，避免重復(fù)計(jì)算 dfs 的結(jié)果（記憶化）def dfs(i: int, j: int) -> int:if i < 0:return 0res1 = dfs(i - 1, j) + energyDrink[j][i]res2 = dfs(i - 2, j ^ 1) + energyDrink[j][i]return max(res1, res2)return max(dfs(n - 1, 0), dfs(n - 1, 1))
# @lc code=end

結(jié)果：

復(fù)雜度分析：

時(shí)間復(fù)雜度：O(n)，其中 n 為數(shù)組 energyDrinkA/energyDrinkB 的長(zhǎng)度。由于每個(gè)狀態(tài)只會(huì)計(jì)算一次，動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度 = 狀態(tài)個(gè)數(shù) × 單個(gè)狀態(tài)的計(jì)算時(shí)間。本題狀態(tài)個(gè)數(shù)等于 O(n)，單個(gè)狀態(tài)的計(jì)算時(shí)間為 O(1)，所以總的時(shí)間復(fù)雜度為 O(n)。

空間復(fù)雜度：O(n)，其中 n 為數(shù)組 energyDrinkA/energyDrinkB 的長(zhǎng)度。保存多少狀態(tài)，就需要多少空間。

解法2：動(dòng)態(tài)規(guī)劃

代碼：

/** @lc app=leetcode.cn id=3259 lang=cpp** [3259] 超級(jí)飲料的最大強(qiáng)化能量*/// @lc code=start
class Solution
{
public:long long maxEnergyBoost(vector<int> &energyDrinkA, vector<int> &energyDrinkB){int n = energyDrinkA.size();vector<array<long long, 2>> dp(n + 2);// 狀態(tài)轉(zhuǎn)移for (int i = 0; i < n; i++){dp[i + 2][0] = max(dp[i + 1][0], dp[i][1]) + energyDrinkA[i];dp[i + 2][1] = max(dp[i + 1][1], dp[i][0]) + energyDrinkB[i];}return max(dp[n + 1][0], dp[n + 1][1]);}
};
// @lc code=end

結(jié)果：

復(fù)雜度分析：

時(shí)間復(fù)雜度：O(n)，其中 n 為數(shù)組 energyDrinkA/energyDrinkB 的長(zhǎng)度。

空間復(fù)雜度：O(n)，其中 n 為數(shù)組 energyDrinkA/energyDrinkB 的長(zhǎng)度。