娄禹的个人博客 – 第 2 页 – Think twice, code once.

LeetCode #322：Coin Change(零钱兑换)

本题是运用完全背包的思想来求一个最小值问题。区别于 01 背包，完全背包问题就是每个物品可以不限个数地放入背包，相应的递推公式也会发生变化。

LeetCode #474：Ones And Zeroes(一和零)

本题依然是 01 背包问题，不过背包有两个维度（m 和 n），是一个二维 01 背包。故 dp 数组要开二维、需要三重循环得出结果。

LeetCode #494：Target Sum(目标和)

乍一看本题和背包问题没关系，但也能转换成 01 背包问题进行求解。另外，不同于 #416 运用 01 背包求最多能装多少东西，本题是运用 01 背包解决排列组合问题，其递推公式略有不同。

LeetCode #435：Non-overlapping Intervals(无重叠区间)

由于本题只要求 “需要移除区间的最小数量”，所以不需要模拟区间被删除的过程。同时本题如果要直接统计重叠区间也不是很方便，我们将问题转化为先求这些区间中非重叠的区间，再用区间总数减去非重叠区间的个数得到答案。