贪心算法

简述

每次都是当前最优解.
缺点: 也许当前呃最优解并不是最后的最优解.就像人生,也许你现在放弃了一些东西以后就收获更多.

适用场景

问题必须能够分解成子问题来解决.**子问题的最优解能够递推到最终问题的最优解.**这种子问题的最优解成为最优子结构.

贪心算法与动态规划不同在于它对每个子问题的解决方案都做出选择,不能回退.

动态规划会保存以前的运算结果,并根据以前的结果对当前进行选择,具备回退功能.

题目分析

122 买卖股票

只要每天的股票价格比前一天的高,就可以买入前一天的股票第二天马上抛出

class Solution {
public:
int maxProfit(vector& prices) {
//动态规划
// if(prices.size()<=1)
// return 0;
// int dp[2][2],x=0;
// dp[0][0]=0;
// dp[0][1]=-prices[0];
// for(int i=1;i<prices.size();i++)
// {
// x=i%2;
// dp[x][0]=max(dp[!x][0],dp[!x][1]+prices[i]);
// dp[x][1]=max(dp[!x][0]-prices[i],dp[!x][1]);
// }
// return dp[x][0];

    //贪心算法
    int ret=0;
    for(int i=1;i<prices.size();i++)
        if(prices[i]>prices[i-1])
            ret+=prices[i]-prices[i-1];
    return ret;
}

};