硬怼动态规划、贪心算法——LeetCode每日一题：买卖股票的最佳时机 II

方法一：暴力法

这题的思路想要理清还是有点麻烦的，如果你连暴力法都想不出来的话，那更别提其他更好的算法了。暴力法的思路为利用递归列出所有可能的情况，在未买入股票的时候有买入和不买入两种情况，在买入股票后有卖出与不卖出两种情况，这样的话就可以把所有情况都列出来，类似于一颗二叉树，如图：

代码实现：

 class Solution {
 int res = 0;

public int maxProfit(int[] prices) {
    if(prices.length < 2){
        return 0;
    }
    getMax(prices,prices.length,true,0,0);
    return res;
}

public void getMax(int[] prices,int len,boolean status,int index,int profit){
    if(index == len){
        res = Math.max(res,profit);
        return;
    }
     //这个递归表示不进行任何操作（买入或卖出）
    getMax(prices,len,status,index + 1,profit);

    //两种情况，status = false表示未买入股票，status = true表示已经买入了股票
    //未买入股票可以选择买入，那么当前利益profit减去当前股票价值
    //已买入股票可以选择卖出，那么当前利益profit加上当前股票价值
    if(status){
        getMax(prices,len,false,index + 1,profit - prices[index]);
    }else{
        getMax(prices,len,true,index + 1,profit + prices[index]);
    }
}
}

方法二：贪心算法（Greedy Algorithm)

算法简介
贪心算法，又名贪婪法，是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好/最优的解。{看着这个名字，贪心，贪婪这两字的内在含义最为关键。这就好像一个贪婪的人，他事事都想要眼前看到最好的那个，看不到长远的东西，也不为最终的结果和将来着想，贪图眼前局部的利益最大化，有点走一步看一步的感觉。}
算法步骤
步骤1：从某个初始解出发；
步骤2：采用迭代的过程，当可以向目标前进一步时，总是做出在当前看来最好的选择，得到一部分解，缩小问题规模；
步骤3：将所有解综合起来。
回到题目中来
既然要在题目中使用贪心算法，那么就要把题目每一步需要执行的步骤变成贪心算法的模式，及每一步都选取最优部分解。
```
 res =  (prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])
     =  prices[3] - prices[0]
```

仔细观察上面的式子，按照贪心算法，在索引为 1、2、3 的这三天，我们做的操作应该是买进昨天的，卖出今天的，虽然这种操作题目并不允许，但是它等价于：“在索引为 0 的那一天买入，在索引为 3 的那一天卖出”。
理解了上面的意思的话，接下来就简单了，只需要在今天买入，并且判断在明天卖出活得的利益是否大于0，大于0的话就执行卖出操作，小于或者等于0的话就不卖出。

时间复杂度：O(n)，只遍历了一次数组
空间复杂度：O(1),，只用了常熟级别的空间

代码实现:

class Solution {

public int maxProfit(int[] prices) {
    if(prices.length < 2){
        return 0;
    }
    int res = 0;
    int index = 1;
    int temp = 0;
    while(index != prices.length){
        temp = prices[index] - prices[index - 1];
        if(temp > 0){
            res = res + temp;
        }
        index++;      
    }
    return res;
}  

}

总结：贪心算法比较适合找出单个最优解，当题解可能有多个最优解时，贪心算法也只能找出一个最优解，所以在需要输出多个最优解时，一般不会使用贪心算法

方法三：动态规划（Dynamic Programming）

这篇文章讲得十分详细：https://www.zhihu.com/question/23995189

其核心思想为：将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。

可以用贪心算法解决的问题，一般情况下都可以用动态规划。因此，不妨从 “状态”、“状态转移方程” 的角度考虑一下，使用动态规划的思路解决这道问题。

解题思路
首先定义状态dp二维数组，dp[天数][状态数]，状态数分为0和1，dp[当前天数][0] 表示这一天不买股票，dp[当前天数][1] 表示这一天买入股票。
确定第一天状态：
如果什么都不做，dp[0][0] = 0；
如果买入股票，当前收益是负数，即 dp[0][1] = -prices[i]；

然后第二天也分为买入股票和不买入，当买入股票时，那么就和第一天买的股票相比较，看哪个花的钱更少（这也是和贪心算法很相似的地方了把）；如果不买股票的话，那么就用第一天买入股票的那个状态再卖出后的利润和什么都不做的利润相比较。

代码实现：

 class Solution {

public int maxProfit(int[] prices) {
    int len = prices.length;
    if(len < 2){
        return 0;
    }
    //0表示不买股票
    //1表示买入股票
    int[][] dp = new int[len][2];
    dp[0][0] = 0;
    dp[0][1] = -prices[0];

    for(int i = 1;i < len;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[len-1][0];
}  

}