知识点
知识点
背包问题
问题描述
背包问题其实是一系列问题的总称，包括01背包问题、完全背包问题、分割等和子集问题等。
这些问题都需要使用到动态规划
贪心算法
算法描述
贪心算法，其实是动态规划算法的一个特例，贪心心算法要满足贪心选择性质。
贪心选择性质简单说就是：每一步都做出一个局部最优的选择，最终的结果就是全局最优。特别注意的是，贪心选择性质是一种特殊性质，只有很少的问题才有
经典问题：
区间调度问题
问题描述
给你很多形如[start,end]的闭区间，请你设计一个算法，算出这些区间中最多有几个互不相交的区间。例如，intvs=[[1,3],[2,4],[3,6]]，这些区间最多有两个区间互不相交，即[[1,3],[3,6]]，你的算法应该返回 2。注意边界相同并不算相交
该问题在生活中的应用广泛，比如你今天有好几个活动，每个活动都可以用区间[start,end]表示开始和结束的时间，请问你今天最多能参加几个活动
贪心解法
正确的思路其实很简单，可以分为以下三步：
1、从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。
2、把所有与 x 区间相交的区间从区间集合 intvs 中删除。
3、重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集。
LeetCode算法
LeetCode算法
416.【分割等和子集】
解题思路：
该问题乍一看和背包问题没有关系，但是如果将该问题转化为：先对集合求和，得出sum，给一个可装载重量为sum/2的背包和N个物品，每个物品的重量为nums[i]。现在让你装物品，是否存在一种装法，能够恰好将背包装满。这样不就是背包问题吗？甚至比01背包问题更加简单。
因此，该题的关键，就是想办法对问题进行转化，转化成我们熟悉的问题。
首先，确定状态和选择，状态为元素和、元素，选择为是否将元素加入元素和中
其次，确定dp数组，dp数组定义为：第dp[i][j]就是前i个物品，装入j大小的背包中，是否能装满。最终我们取sum/2的容量时，整个数组是否能装满sum/2即可。
然后，base case。base case就是，当dp[..][0] = true和dp[0][..] = false，因为背包没有空间的时候，就相当于装满了，而当没有物品可选择的时候，肯定没办法装满背包
最后，状态转移方程的确定。根据上述结论，可以知道，dp[i][j]是否装满sum/2，只要前i-1个装满或者第i个刚好装满二者之一都可。
518.【零钱兑换II】
解题思路：
该问题，其实可以转化为背包问题，有一个背包，最大容量为amount，有一系列物品coins，每个物品的重量为coins[i]，每个物品的数量无限。这其实就是完全背包问题。
首先，确定状态和选择。
其次，确定dp数组。dp数组定义为：若只使用前i个物品，当背包容量为j时，有dp[i][j]种方法可以装满背包，以零钱问题来说，就是若只使用coins中的前i个硬币的面值，若想凑出金额j，有dp[i][j]种凑法。
然后，确定base case。base case就是dp[0][..] = 0， dp[..][0] = 1。因为如果不使用任何硬币面值，就无法凑出任何金额；如果凑出的目标金额为 0，那么不选择就是唯一的一种凑法。
最后，写出状态转移方程。如果你不把这第i个物品装入背包，也就是说你不使用coins[i]这个面值的硬币，那么凑出面额j的方法数dp[i][j]应该等于dp[i-1][j]，继承之前的结果；如果你把这第i个物品装入了背包，也就是说你使用coins[i]这个面值的硬币，那么dp[i][j]应该等于dp[i][j-coins[i-1]]。因为dp定义为共有多少种凑法，因此dp[i][j]应该为两种选择的凑法之和。
遍历为从前向后遍历。
435.【无重叠区间】
解题思路：
求最小数量，很可能是动态规划，又因为该题就是区间调度问题，因此使用贪心算法来解即可。
452.【用最少数量的箭引爆气球】
解题思路：
该问题仍然是区间调度问题
京公网安备 11010502036488号