贪心算法思想和例题讲解

贪婪的商人总是想获得最大的利润，每一次交易都想获得最大利润，而不为长远考虑。

定义

贪婪算法：总是做出在当前最好的选择。而不是从整体上考虑，它所做出的仅仅是在局部上的最优解。所以贪婪算法必须保证无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

步骤

• 把求解的问题分成若干个子问题；
• 对每一子问题求解，得到子问题的局部最优解；
• 把子问题的解局部最优解合成原来解问题的一个解。

例题：买卖股票的最佳时机问题

根据题目的意思，当天卖出以后，当天还可以买入，所以其实可以第三天卖出，第三天买入，第四天又卖出（（5-1）+ （6-5） === 6 - 1）。所以算法可以直接简化为只要今天比昨天大，就卖出。所以我们只要保证今天比昨天大这一条件，就可以保证我们的结果是最优的！

public class Solution {
    public int MaxProfit(int[] prices) {
        int ans=0;
        for(int i=1;i<=prices.Length-1;i++)//对应上述步骤一
        {
            if(prices[i]>prices[i-1])//对应上述步骤二
            {
                ans+=prices[i]-prices[i-1];//对应上述步骤三
            }
        }
        return ans;
    }
}

贪婪算法和动态规划的区别和联系

相同点：

1. 都分解为子问题
2. 都为推导算法

不同点：

1. 动态规划中每一步的解往往需要依赖其及子问题的解，而贪婪算法只与当前这一步有关，只求出这一步的最优解。
2. 动态规划往往是自下而上，贪婪算法往往是自上而下。

贪婪算法的其它例题：

欢迎评价和指正，谢谢！