LeetCode: 121. 买卖股票的最佳时机
1.思路
暴力解法、贪心也算比较符合思维，动规不容易想到，且状态处理不易处理
股票每天的状态为持有或不持有：声明dp数组：int[][] dp = new int[prices.length][2];
确定含义：dp[i][0] 表示第i天持有股票的最大收益，dp[i][1] 表示第i天不持有股票的最大收益。
初始化：dp[0][0] = -prices[0];dp[0][1] = 0;
2.代码实现
1// 动规 2class Solution { 3 public int maxProfit(int[] prices) { 4 if (prices.length == 0 || prices == null) { 5 return 0; 6 } 7 // dp[i][0] 表示第i天持有股票的最大收益 8 // dp[i][1] 表示第i天不持有股票的最大收益 9 int[][] dp = new int[prices.length][2]; 10 dp[0][0] = -prices[0]; 11 dp[0][1] = 0; 12 for (int i = 1; i < prices.length; i++) { 13 dp[i][0] = Math.max(dp[i - 1][0], -prices[i]); 14 dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]); 15 } 16 return dp[prices.length - 1][1]; 17 } 18} 19
1// 暴力解法 2class Solution { 3 public int maxProfit(int[] prices) { 4 int profit = 0; 5 for (int i = 0; i < prices.length; i++) { 6 for (int j = i + 1; j < prices.length; j++) { 7 profit = Math.max(profit, prices[j] - prices[i]); 8 } 9 } 10 return profit; 11 } 12} 13// 贪心算法 14class Solution { 15 public int maxProfit(int[] prices) { 16 int low = Integer.MAX_VALUE; 17 int res = 0; 18 for (int i = 0; i < prices.length; i++) { 19 low = Math.min(prices[i], low); 20 res = Math.max(prices[i] - low, res); 21 } 22 return res; 23 } 24}
3.时间复杂度
时间复杂度：O(n).
空间复杂度：O(1).
LeetCode: 122.买卖股票的最佳时机II
122. 买卖股票的最佳时机 II - 力扣（LeetCode）
1.思路
动规真香，可以一个套路解决多题
和上一题类似，每天股票有两种状态，持有或不持有。
递推公式：
第i天持有，有两种情况：①第i-1天就持有；②第i天买入持有；
第i天不持有，有两种情况：①第i-1天就不持有；②第i天卖出，说明第i-1天持有（包含了当天买入卖出）
2.代码实现
1class Solution { 2 public int maxProfit(int[] prices) { 3 if (prices.length == 0 || prices == null) { 4 return 0; 5 } 6 int[][] dp = new int[prices.length][2]; 7 // 8 // 9 dp[0][0] = -prices[0]; 10 dp[0][1] = 0; 11 for (int i = 1; i < prices.length; i++) { 12 // 第 i 天持有股票：①当天买入且前一天不持有；②前一天持有 13 dp[i][0] = Math.max(dp[i - 1][1] - prices[i], dp[i - 1][0]); 14 // 第 i 天不持有股票：①第 i 天卖出；②第i-1天就不持有 15 dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]); 16 } 17 return dp[prices.length - 1][1]; 18 } 19} 20
3.时间复杂度
时间复杂度：O(n).
空间复杂度：O(1).
