背包问题和单调栈

背包问题（动态规划）

动态五步曲

• dp数组及下标索引的含义
• 递推公式
• dp数组如何初始化
• 遍历顺序
• 打印dp数组

01背包：n种物品，有一个,二维数组遍历顺序可以颠倒，（滚动数组）一维数组遍历顺序不可颠倒

完全背包：n种物品，有无限多个

多重背包：n种物品，数量各不相同

01背包

思路：

dp[i][j] ---> i是[0, i]之间的任意物品，放容量为j的背包中，所能得到的最大价值为dp[i][j]，分不放物品和放物品的情况。
dp[j] ---> 容量为j的背包所能装的最大价值为dp[j]，分为不放物品和放物品的情况，滚动数组倒序遍历，保证每一个物品只被添加一次。

// 01背包，滚动数组
for 物品for 背包（倒序 --> 每个物品只被添加一次 ），正序导致，物品被添加两次，不符合每个物品只能用一次

单调栈模版：

使用场景：比当前元素（左/右）大/小的数

// 输入 int[]  nums
int len = nums.length;
// 双端队列，既可以实现 栈 还可以实现 队列
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()]) {// 当前索引下标 - 栈顶元素下标int res = i - stack.pop();stack.pop();}}stack.push(nums[i]);
}
return res;