什么是動態規劃法？

簡單說，動態規劃（Dynamic Programming，簡稱 DP） 是一種**「把復雜問題拆解成小問題，通過解決小問題來解決大問題」**的方法。
核心思路有兩個：
1.拆分問題：把原問題拆成多個相似的「子問題」（比如求 “整個數組的最大子數組和” 可以拆 成 “以每個元素結尾的最大子數組和”）。
2.記住答案：用一個表格（或變量）記錄子問題的答案，避免重復計算（這一步叫「記憶化」）。

用動態規劃解決 “最大子數組和” 的標準思路

以 nums = [-2, 1, -3, 4] 為例：
1.定義子問題：設 dp[i] 為「以第 i 個元素結尾的最大子數組和」。

• 比如 dp[0] 是 “以 -2 結尾的最大和” → 只能是 -2。
• dp[1] 是 “以 1 結尾的最大和” → 要么單獨用 1，要么用 dp[0] + 1（即 -2 + 1 = -1），取大的那個 → 1。

2.找規律（狀態轉移方程）：dp[i] = max(nums[i], dp[i-1] + nums[i])（要么從當前元素重新開始，要么接上前面的子數組）
3.計算所有子問題：

• dp[0] = -2
• dp[1] = max(1, -2+1) = 1
• dp[2] = max(-3, 1-3) = -2
• dp[3] = max(4, -2+4) = 4

4.求最終答案：所有 dp[i] 中的最大值 → 4。
我們現在用的方法，其實是動態規劃的 “升級版”
上面的標準思路需要一個 dp 數組來存所有子問題的答案（空間復雜度 O(n)），但我們可以優化：
觀察發現：計算 dp[i] 只需要前一個 dp[i-1] 的值，不需要整個數組。
所以可以用一個變量 sum 代替 dp 數組（sum 就代表當前的 dp[i]），這樣空間復雜度就降到了 O(1)。
這就是我們現在用的方法：

• sum 等價于 dp[i]（當前子問題的答案）。
• sum = max(nums[i], sum + nums[i]) 就是狀態轉移方程。
• res 用來記錄所有 sum 中的最大值（即最終答案）。

總結

• 標準動態規劃：用數組存所有子問題答案，思路直觀，空間稍大。
• 我們現在的方法：用單個變量代替數組，核心邏輯不變，是動態規劃的「空間優化版」。

題目

https://leetcode.cn/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-100-liked

給你一個整數數組 nums ，請你找出一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。 子數組是數組中的一個連續部分。
示例 1： 輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]輸出：6解釋：連續子數組 [4,-1,2,1] 的和最大，為
6 。 示例 2： 輸入：nums = [1]輸出：1 示例 3： 輸入：nums = [5,4,-1,7,8]輸出：23

題解

class Solution {public int maxSubArray(int[] nums) {// 把sum初始化為數組第一個元素int sum = nums[0];// 結果也初始化為第一個元素（因為最大和至少是它自己）int res = nums[0];// 從第二個元素開始遍歷（索引1）for (int i = 1; i < nums.length; i++) {// 同樣先判斷：之前的sum是否有用if (sum > 0) {// 有用就累加當前元素sum += nums[i];} else {// 沒用就從當前元素重新開始sum = nums[i];}// 更新最大和res = Math.max(res, sum);}return res;}
}

過程解讀（結合 “攢錢” 例子）

• 初始狀態：手里先拿著第一天的錢 sum=-1（虧了 1 塊），歷史最多錢 res=-1。
• 第二天（元素 2）：之前手里是虧的（sum=-1），不如直接拿今天的 2 塊，sum 變成 2。歷史最多錢更新為 2。
• 第三天（元素 - 3）：手里有 2 塊（正數），雖然今天花了 3 塊，但還是加上試試，sum=2-3=-1。歷史最多錢還是 2（因為 - 1 < 2）。
• 第四天（元素 4）：手里是 - 1（虧的），直接拿今天的 4 塊，sum 變成 4。歷史最多錢更新為 4。
• 第五天（元素 - 1）：手里有 4 塊（正數），今天花 1 塊，加上后 sum=4-1=3。歷史最多錢還是 4（因為 3 < 4）。
  最終結果是 4，對應最大子數組 [4]（或者理解為 “只拿第四天的錢最劃算”）。