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