阿竺 ·1. 前言
動態規劃（Dymamic Programming，簡稱 DP）應該是面試中出現頻率最多并且公認難度最大的一類題型，動態規劃問題非常靈活，沒有統一的模板。動態規劃中最簡單的問題，例如爬樓梯，狀態轉移方程非常簡單，但是大部分問題都沒有通用的狀態轉移方程，所以如果缺乏對DP問題的練習，在筆試和面試中就有卡殼無從下手的風險。候選人的目標應該是盡可能的找到不同題目之間的相似點并舉一反三。
2. 最大子數組和
面試官提問：給定一個數組，求解數組中連續子樹組的最大和。
題目解析：
求解最大子數組求和問題是來源于算法網站LeetCode的經典題目，題目鏈接：https://leetcode.com/problems/maximum-subarray/。
我們以小型數據的數組作為樣例分析，什么是連續子數組的最大和：
樣例輸入：[-2,1,-3,4,-1,2,1,-5,4]
樣例輸出：6
樣例解釋：連續子數組 [4,-1,2,1] 的和最大，求和結果為6。
這里需要特別明確子樹組和子序列的區別，
（1）子樹組定義：一個或者連續多個數組中元素組成一個子數組；
（2）子序列定義：在原來數組中找出一部分組成的序列。
結論：子樹組一定是連續的數字，但是子序列只需要保證前后順序上的有序，數字之間不一定連續。
在明確子數組定義之后，我們用一句話概括 DP 的核心解題思路：我們要找到某個子問題的最優解，然后在它的幫助下，找到下一個子問題的最優解。
例如對于爬樓梯問題，對于 n 個臺階，每次能夠跳一個臺階或者兩個臺階，我們知道對于第 k 個臺階，一定是從第 k-1 個臺階再跳一個臺階，或者是從第k-2個臺階再跳兩個臺階上來，所以只需要知道第 k-1 個臺階的路徑個數和第k-2個臺階的路徑個數，求和就是最終的答案。其中第 k-1 和第 k-2 個臺階的路徑就是子問題。
將上述的語義切換到算法上來，就是需要找到狀態轉移方程以及狀態的初始值。
最大子樹組和問題中，狀態的初始含義非常明確：如果數組的長度為空，那么不存在子樹組，直接返回最大和為零。
初始狀態結果為零的含義是，最后返回的最大子樹組和一定不是負數，因為和為負數還不如直接用空數組返回零。
對于一般子問題，我們假設 dp[i] 表示以 nums[i] 作為子樹組末尾元素的前i個數字構成的子樹組的最大和，nums[i]表示數組中的第i個元素。舉例來說，對于數組[a1，a2，a3]，dp[2] 只有三種構成可能：[a1，a2，a3]，[a2，a3]，[a3]，都是以 a3 作為子數組結尾元素。
那么假設已經遍歷到了第i個數字，如果 dp[i-1] 小于零，說明數組的前 i-1 個子樹組的和最大也是負數，前面說過，負數對于求解結果是沒有幫助的，所以如果 dp[i-1] 小于零，dp[i] 直接選擇 nums[i] 作為只有一個元素的子數組，和最大值就是 nums[i]。如果 dp[i-1] 大于零，說明加上前面的子樹組會讓結果更大，那么需要加上。
上面的語義用dp方程表示如下：
dp[i] = 0 如果nums.length=0；
dp[i] = nums[i] 如果dp[i-1] < 0；
dp[i] = nums[i] + dp[i-1]，如果dp[i-1] > 0 。
最后，我們需要返回的是 dp 數組中的最大值。
從狀態轉移方程可以看出，我們其實只需要 dp[i-1]，所以使用一個臨時變量去保存它，能將空間復雜度降低到O（1）。示例：
public int maxSubArray(int[] nums) {
//邊界條件判斷
if (nums.length == 0){
return 0;
}
//表示dp[i-1]
int prev = nums[0];
//表示dp[i]
int cur = nums[0];
//結果
int max = nums[0];
for (int i = 1; i < nums.length; i++){
if (prev > 0){
//如果dp[i-1] > 0
cur = prev + nums[i];
} else {
//如果dp[i-1] <= 0
cur = nums[i];
}
max = Math.max(max, cur);
prev = cur;
}
return max;
}
3. 小結
本章節介紹了動態規劃中最簡單的一種問題，就是在數組中找到滿足要求的極大值或者極小值，通常只需要構建一個簡潔的狀態轉移方程就可以解決問題。如果狀態轉移方程中只涉及到連續的兩個或者三個位置的值變化，甚至可以將狀態數組壓縮到單個變量，將空間復雜度從O（n）優化到O（1）。
2025 imooc.com All Rights Reserved |