Python 動態規劃（DP）套路總結

在解決算法問題時，動態規劃（DP） 是一種非常常見的優化技巧，它可以通過保存子問題的結果來避免重復計算，從而減少時間復雜度。Python 提供了非常方便的語法特性，使得實現動態規劃變得相對簡單。下面是一些常見的 Python 語法 和 DP 解題套路。

1. Python 語法和技巧

1.1 列表初始化

在 Python 中，動態規劃通常需要一個數組來存儲子問題的解，常見的初始化方法有：

• 一維數組：

  dp = [0] * n  # 初始化一個長度為 n 的數組，元素均為 0
  

• 二維數組：

  dp = [[0] * m for _ in range(n)]  # 初始化一個 n x m 的二維數組，元素均為 0
  

• 處理邊界情況：
  如果問題涉及到無效值（例如負無窮），可以初始化為非常小的數字：

  dp = [-float('inf')] * n  # 初始化為負無窮
  

1.2 枚舉排列

• 枚舉排列：通常用于動態規劃中，確定所有的選擇路徑：

  for i in range(n):for j in range(i, n):  # 遍歷子數組# 在這里進行狀態轉移
  

• 利用索引生成排序后的順序：

  sorted_idx = sorted(range(len(arr)), key=lambda i: arr[i])  # 排序并記錄原始索引
  

2. 動態規劃（DP）解題套路

2.1 狀態定義

首先，需要定義一個或多個狀態，表示每個子問題的結果。常見的狀態定義如下：

• dp[i] 表示前 i 個元素的最大和或最小值
• dp[i][j] 表示在第 i 個位置選擇了 j 種操作后的最優解
• 對于某些題目，可能需要額外記錄其他信息，如最大或最小值、索引等。

2.2 狀態轉移方程

根據題目要求，寫出從一個狀態轉移到另一個狀態的遞推公式。一般來說，轉移方程會根據前一個狀態的結果來更新當前狀態。

2.3 邊界條件

動態規劃通常從小的子問題開始，需要明確邊界條件：

• dp[0] 可能是初始化的最小值。
• dp[1] 可能是初始值或第一個元素的特殊處理。

2.4 最終解的選擇

在動態規劃的過程中，我們最終希望找到全局最優解（例如最大值或最小值）。通常，我們需要通過 max(dp) 或 min(dp) 來獲取結果。

---

3. 題目解析與動態規劃解法

題目：1186. 刪除一次得到子數組最大和

題目描述

給定一個整數數組 arr，返回它的某個非空子數組（連續元素）在執行一次可選的刪除操作后，所能得到的最大元素總和。換句話說，你可以從原數組中選出一個子數組，并可以決定要不要從中刪除一個元素（只能刪一次哦），刪除后該子數組中至少應當有一個元素。

示例

arr = [1,-2,0,3]
輸出: 4

解釋：

• 我們可以選擇子數組 [1, -2, 0, 3]，刪除 -2，得到 [1, 0, 3]，最大和為 4。

解法思路

對于這個問題，我們可以使用 動態規劃（DP） 來處理。考慮兩種情況：

1. 不刪除任何元素 的情況下，子數組的最大和。
2. 刪除一個元素后，子數組的最大和。

1. 定義狀態

• dp[i][0]：表示到第 i 個元素為止，不刪除任何元素時的最大和。
• dp[i][1]：表示到第 i 個元素為止，刪除一個元素后的最大和。

2. 狀態轉移方程

• dp[i][0]：可以選擇加入當前元素，或者從當前元素開始一個新的子數組：

  dp[i][0] = max(arr[i], dp[i-1][0] + arr[i])
  

• dp[i][1]：可以選擇刪除當前元素，或者刪除前一個元素并加上當前元素：

  dp[i][1] = max(dp[i-1][0], dp[i-1][1] + arr[i])
  

3. 邊界條件

• dp[0][0] = arr[0]，表示子數組只有第一個元素的情況。
• dp[0][1] = -inf，表示第一個元素不能刪除，因為至少要保留一個元素。

4. 最終解

我們需要考慮兩種情況的最大值：

• dp[i][0] 表示不刪除元素的最大和。
• dp[i][1] 表示刪除一個元素后的最大和。

最終的解是 max(max(dp[i][0] for i in range(n)), max(dp[i][1] for i in range(n)))。

代碼實現

class Solution:def maximumSum(self, arr: List[int]) -> int:n = len(arr)# 初始化 dp 數組，初始值為負無窮dp = [[-2e9, -2e9] for _ in range(n)]# 初始化第一個元素的情況dp[0][0] = arr[0]dp[0][1] = float('-inf')  # 刪除第一個元素不合法# 動態規劃遍歷for i in range(1, n):dp[i][0] = max(arr[i], dp[i - 1][0] + arr[i])  # 不刪除dp[i][1] = max(dp[i - 1][0], dp[i - 1][1] + arr[i])  # 刪除一個元素# 返回最大結果return max(max(dp[i][0] for i in range(n)), max(dp[i][1] for i in range(n)))

解析：

1. 初始化：我們初始化了 dp 數組，并為第一個元素設定了邊界條件。
2. 狀態轉移：我們通過遍歷 arr 數組，逐步計算 dp[i][0] 和 dp[i][1]，表示不刪除元素和刪除元素后的最大和。
3. 返回結果：最后返回 dp 數組中最大的值，即為子數組的最大和。

時間復雜度與空間復雜度：

• 時間復雜度：O(n)，我們只遍歷了一次數組，并進行常數時間的計算。
• 空間復雜度：O(n)，需要一個大小為 n 的動態規劃數組。

---

總結

動態規劃（DP）是解決子問題最優解的強大工具。在此題中，我們利用了動態規劃的狀態定義和轉移方程來解決刪除一次元素后的子數組最大和問題。在處理此類問題時，理解狀態定義與轉移方程至關重要，它能夠幫助我們高效地得出最終的最優解。
兩種狀態 沒有行使權力的最大數組和 行使權力后的最大數組和
沒有行使權力可以另起爐灶一個新的或者繼承之前的
行使權力的可以繼承之前的，或者行使權力不刪集成沒有行使權力的