备战算法国赛ing

Day 1 背包问题

01背包问题

有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积。

现在从 n 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。

DP核心：找变量之间的状态转移方程

代码：

接雨水问题

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

核心是要理解，对于每一个位置（数组中每一个数），它能接的雨水量取决于：

min(左边最大高度, 右边最大高度) - 当前高度