背包問(wèn)題（動(dòng)態(tài)規(guī)劃）

動(dòng)態(tài)五步曲

• dp數(shù)組及下標(biāo)索引的含義
• 遞推公式
• dp數(shù)組如何初始化
• 遍歷順序
• 打印dp數(shù)組

01背包：n種物品，有一個(gè),二維數(shù)組遍歷順序可以顛倒，（滾動(dòng)數(shù)組）一維數(shù)組遍歷順序不可顛倒

完全背包：n種物品，有無(wú)限多個(gè)

多重背包：n種物品，數(shù)量各不相同

01背包

思路：

dp[i][j] ---> i是[0, i]之間的任意物品，放容量為j的背包中，所能得到的最大價(jià)值為dp[i][j]，分不放物品和放物品的情況。
dp[j] ---> 容量為j的背包所能裝的最大價(jià)值為dp[j]，分為不放物品和放物品的情況，滾動(dòng)數(shù)組倒序遍歷，保證每一個(gè)物品只被添加一次。

// 01背包，滾動(dòng)數(shù)組
for 物品for 背包（倒序 --> 每個(gè)物品只被添加一次 ），正序?qū)е?#xff0c;物品被添加兩次，不符合每個(gè)物品只能用一次

單調(diào)棧模版：

使用場(chǎng)景：比當(dāng)前元素（左/右）大/小的數(shù)

// 輸入 int[]  nums
int len = nums.length;
// 雙端隊(duì)列，既可以實(shí)現(xiàn) 棧 還可以實(shí)現(xiàn) 隊(duì)列
Deque<Integer> stack = new LinkedList<>();		// 棧中存儲(chǔ)的是元素的索引
for (int i = 0; i <len; i++) {// 遞增棧if(nums[i] > nums[stack.peek()]) {// 如果需要存儲(chǔ)可以提前 pop()while (!stack.isEmpty()  && nums[i] > nums[stack.peek()]) {// 當(dāng)前索引下標(biāo) - 棧頂元素下標(biāo)int res = i - stack.pop();stack.pop();}}stack.push(nums[i]);
}
return res;