一、理论
贪心（Greedy）算法：在对问题求解时，总是做出在当前看来是最好的选择。
由于贪心算法每一次操作都需要取最大值或最小值，所以通常需要对数组排序。
适用Greedy 的场景：
问题能够分成子问题来解决，子问题的最优解能递推到最终问题的最优解。 如果不能使用贪心算法，只需要举出反例即可。
贪心选择性质的证明（利用反证法，证明贪心算法的正确性）：
贪心算法为A，最优算法为O；如果证明过程中发现A完全能替代O，且不影响求出最优解，则出现矛盾。
贪心算法与动态规划的不同：
贪心对每个子问题的解决方案都作出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
二、典型例题
①：买卖股票的最佳时期（LC122）
方法1：贪心（针对此问题的特殊解法，因为一天可以买卖无数次），一次遍历，只要只要后一天比前一天大 就在今天买入然后明天卖出（时间复杂度：O(n)）
class Solution { public int maxProfit(int[] prices) { int res = 0; for (int i = 0; i < prices.length - 1; i++) { if (prices[i] < prices[i+1]){ res += prices[i+1] - prices[i]; } } return res; } }
方法2：DP（解决股票问题的通用方法）------（时间复杂度：O(n)）
class Solution { public int maxProfit(int[] prices) { // 状态的定义：dp[i][j]表示第i天交易完后 持股(j=1)或不持股(j=0)状态下 的最大利润， /* int n = prices.length; int[][] dp = new int[n][2]; dp[0][0] = 0; dp[0][1] = -prices[0]; for (int i = 1; i < n; i++) { dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]); dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]); } return dp[n - 1][0]; */ /** * 空间压缩 , 每一天的状态只与前一天的状态有关， */ int n = prices.length; int dp0 = 0, dp1 = -prices[0]; for (int i = 1; i < n; i++) { int newDp0 = Math.max(dp0, dp1 + prices[i]); int newDp1 = Math.max(dp1, dp0 - prices[i]); dp0 = newDp0; dp1 = newDp1; } return dp0; } }
三、扩展例题
第一组：LeetCode455. 分发饼干、LeetCode392. 判断子序列
第二组（贪心算法与动态规划）：LeetCode435. 无重叠区间