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