LeetCode122. 买卖股票的最佳时机 II（动态规划、贪心算法）

叁歲伎倆 2022-01-31 10:41 214阅读 0赞

# 题目： #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5MzUwMQ_size_16_color_FFFFFF_t_70]

# 贪心算法 #

/*** * 贪心算法：只要第二天的价格比今天高，就第一天买，第二天卖 * @param prices * @return */
        public int maxProfix(int[] prices) { 
            if (prices == null || prices.length == 0 || prices.length == 1) { 
                return 0;
            }
            int max = 0;
            for (int i = 0; i < prices.length - 1; i++) { 
                if(prices[i+1] - prices[i] > 0){ 
                    max += prices[i + 1] - prices[i];
                }
            }
            return max;
        }

#### 贪心算法原理 ####

[原理链接][Link 1]

# 动态规划 #

public class Soulution { 
        public int maxProfix(int[] prices) { 
            if (prices == null || prices.length == 0 || prices.length == 1) { 
                return 0;
            }
    
            int[][] dp = new int[prices.length][2];
            dp[0][0] = 0;
            dp[0][1] = -7;
            for (int i = 1; i < prices.length; 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[prices.length - 1][0];
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5MzUwMQ_size_16_color_FFFFFF_t_70]: /images/20220131/7d9babc9cc6c43ef882e42bb36ddda3d.png
[Link 1]: https://blog.csdn.net/qq_23997101/article/details/76651516#commentBox