背包問題（動態(tài)規(guī)劃）

動態(tài)五步曲

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

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

完全背包：n種物品，有無限多個

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

01背包

思路：

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

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

單調(diào)棧模版：

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

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