LeetCode #474：Ones And Zeroes(一和零) 题目描述 本题依然是 01 背包问题，不过背包有两个维度（m 和 n），是一个二维 01 背包。故 dp 数组要开二维、需要三重循环得出结果。 阅读全文
LeetCode #494：Target Sum(目标和) 题目描述 乍一看本题和背包问题没关系，但也能转换成 01 背包问题进行求解。另外，不同于 #416 运用 01 背包求最多能装多少东西，本题是运用 01 背包解决排列组合问题，其递推公式略有不同。 阅读全文
LeetCode #435：Non-overlapping Intervals(无重叠区间) 题目描述 由于本题只要求 “需要移除区间的最小数量”，所以不需要模拟区间被删除的过程。同时本题如果要直接统计重叠区间也不是很方便，我们将问题转化为先求这些区间中非重叠的区间，再用区间总数减去非重叠区间的个数得到答案。 阅读全文
LeetCode #135：Candy Distribution(分发糖果) 题目描述 本题需要把整个问题一分为二去看。先确定右边孩子的评分大于左边的情况，即顺序遍历 ratings 数组，只要右边孩子的评分比左边大，右边孩子就多一个糖果（局部最优），从而使得相邻的孩子中，评分高的右孩子都能相对左孩子多获得一颗糖；同理再倒序遍历 ratings 数组，使得左边孩子的评分高于右边孩子时，多给一颗糖。 阅读全文