贪心算法思想和例题讲解
贪婪的商人总是想获得最大的利润，每一次交易都想获得最大利润，而不为长远考虑。
定义
贪婪算法：总是做出在当前最好的选择。而不是从整体上考虑，它所做出的仅仅是在局部上的最优解。所以贪婪算法必须保证无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
步骤
-
把求解的问题分成若干个子问题； 对每一子问题求解，得到子问题的局部最优解； 把子问题的解局部最优解合成原来解问题的一个解。
例题：买卖股票的最佳时机问题
根据题目的意思，当天卖出以后，当天还可以买入，所以其实可以第三天卖出，第三天买入，第四天又卖出（（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;
}
}
贪婪算法和动态规划的区别和联系
相同点：
- 都分解为子问题
- 都为推导算法
不同点：
- 动态规划中每一步的解往往需要依赖其及子问题的解，而贪婪算法只与当前这一步有关，只求出这一步的最优解。
- 动态规划往往是自下而上，贪婪算法往往是自上而下。
贪婪算法的其它例题：
欢迎评价和指正，谢谢！
