Day48題目

LeetCode121買股票的最佳時機1

核心思想:可以使用貪心,選擇左邊最小的和右邊最大的,也可以動態規劃,需要保存是否持有股票的狀態,dp[i][0]表示第i天,不持有股票,dp[i][1]表示第i天持有

class Solution {public int maxProfit(int[] prices) {int[][] dp = new int[prices.length+1][2];dp[0][0] = 0;dp[0][1] = -prices[0];for(int i = 1  ; i < prices.length; i ++){// 第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],-prices[i]);}return dp[prices.length-1][0];}
}

LeetCode122買股票的最佳時機2

核心思想:也可以用貪心,只要比后一天小,就今天買,明天賣. 動態規劃dp數組和上面一道題一樣,只不過dp持有股票的含義略微變化

class Solution {public int maxProfit(int[] prices) {int[][] dp = new int[prices.length][2];dp[0][0] = 0;dp[0][1] = -prices[0];for(int i = 1;  i < prices.length ; i ++){// 第i天沒有股票,可以是前一天有,今天賣了,或者前一天也沒有dp[i][0] = Math.max(dp[i-1][1]+prices[i], dp[i-1][0]);// 第i天有股票,可以是前一天沒有,今天買了,或者前一天就有.   兩道題唯一的區別,上面的只能買一次,所以可以是 昨天沒有,今天買,昨天也可以是之前什么時候賣完了dp[i][1] = Math.max(dp[i-1][0]-prices[i], dp[i-1][1]);}return dp[prices.length-1][0];}
}