买卖股票的最佳时机

这题的特点就是只能买卖股票一次: 在某一天买入然后在某一天卖掉

贪心解法: 这个比较容易理解, 就是取坐左边最小值, 然后取右边最大值, 直接拉代码

class Solution {public int maxProfit(int[] prices) {int low = Integer.MAX_VALUE;int result = 0;for(int i = 0; i < prices.length; i++){//找到左边最小的low = Math.min(low, prices[i]);//直接取值result = Math.max(result, prices[i] - low);}return result;}
}

动规:

1. 数组定义: dp[i][0]表示第i天持有股票所得最多现金(一开始现金是0, 那么持有后就是-prices[i]), dp[i][1]表示第i天不持有股票所得最多现金
2. 确定递推公式,
   1. 如果第i天持有股票, 即dp[i][0]
      1. 如果i-1天就持有股票, 那么维持现状, 现在的现金就是昨天持有股票的所得现金(dp[i-1][0])
      2. 第i天才买入股票, 那么就是股票的现金-price[i], 比较两者最大值
   2. 如果第i天不持有股票, 即dp[i][1]
      1. 如果i-1天就不持有股票, 那么维持现状, 就是昨天没股票的现金(dp[i-1][1])
      2. 如果第i天卖掉股票, 按照股票价格+之前只有股票的情况(prices[i] + dp[i-1][0])
3. 初始化:可以看出来基础都是从dp[i][0]何dp[i][1]推出 , dp[0][0]表示第0天就持有股票了, 所以dp[0][0] -= prices[0], dp[0][1]不持有股票就肯定是0
4. 从前向后遍历
5. 最后的dp[len - 1][1]就是结果, 因为不持有股票的情况肯定比持有时有钱

class Solution {public int maxProfit(int[] prices) {int len = prices.length;if(prices == null || len == 0){return 0;}//创建一个二维dp数组int[][] dp = new int[len + 1][2];//初始化dp[0][0] -= prices[0];dp[0][1] = 0;//开始遍历for(int i = 1; i < len; i++){//持有股票的情况dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);//不持有股票的情况dp[i][1] = Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0]);}return dp[len - 1][1];}
}

也可以简化为一维数组版本

class Solution {public int maxProfit(int[] prices) {int len = prices.length;if(len == 0 || prices == null){return 0;}int[] dp = new int[2];//一样进行初始化dp[0] -= prices[0];dp[1] = 0;//开始遍历, 这里往后推了一天for(int i = 1; i <= len; i++){//有股票: 之前就有/今天买的dp[0] = Math.max(dp[0], -prices[i - 1]);//无股票: 本来就没有, 和今天卖掉的dp[1] = Math.max(dp[1], prices[i - 1] + dp[0]);}return dp[1];}
}

买卖股票的最佳时机II

上一题是只能买卖一次, 这里是可以无限买卖

贪心算法:

之前已经提过, 就是相当于每天都交易, 然后只要交易结果是正数就加起来

class Solution {public int maxProfit(int[] prices) {int res = 0;for(int i = 1; i < prices.length; i++){res += Math.max(prices[i] - prices[i-1], 0);}return res;}
}

动态规划:

这里的dp数组定义和上一题是一模一样的, 唯一不同的地方，就是推导dp[i][0]的时候，第i天买入股票的情况

第i天持有股票, 要么是之前就有, 要么是第i天才买, 对于后者: 需要用之前已经有的现金-第i天的price

第i天不持有股票, 要么是之前就无, 要么是第i天才卖掉, 对于后者: 也是今天价格+之前有的情况

class Solution {public int maxProfit(int[] prices) {int len = prices.length;if(len == 0 || prices == null){return 0;}int[][] dp = new int[len + 1][2];dp[0][0] -= prices[0];dp[0][1] = 0;//开始遍历for(int i = 1; i < len; i++){//持有股票---之前就有/今天买的(要加上之前的钱)dp[i][0] = Math.max(dp[i - 1][0], -prices[i] + dp[i - 1][1]);//没有股票----之前就没/今天卖掉的dp[i][1] = Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0]);}return dp[len - 1][1];}
}

优化版, 记住两点:

1. 全部变成一维数组里, 所以直接把第一个中括号里的东西全部砍掉
2. 因为这里往后推了一天, 这里的遍历要≤len; 同时price的价格要-1才是对的

class Solution {public int maxProfit(int[] prices) {int len = prices.length;if(len == 0 || prices == null){return 0;}int[] dp = new int[2];dp[0] -= prices[0];dp[1] = 0;//开始遍历for(int i = 1; i <= len; i++){//持有股票---之前就有/今天买的(要加上之前的钱)dp[0] = Math.max(dp[0], -prices[i - 1] + dp[1]);//没有股票----之前就没/今天卖掉的dp[1] = Math.max(dp[1], prices[i - 1] + dp[0]);}return dp[1];}
}