青蛙過(guò)河1
給你一個(gè)下標(biāo)從 0 開(kāi)始的整數(shù)數(shù)組 stones ，數(shù)組中的元素 嚴(yán)格遞增 ，表示一條河中石頭的位置。
一只青蛙一開(kāi)始在第一塊石頭上，它想到達(dá)最后一塊石頭，然后回到第一塊石頭。同時(shí)每塊石頭 至多 到達(dá) 一次。
一次跳躍的 長(zhǎng)度 是青蛙跳躍前和跳躍后所在兩塊石頭之間的距離。
更正式的，如果青蛙從 stones[i] 跳到 stones[j] ，跳躍的長(zhǎng)度為 |stones[i] - stones[j]| 。
一條路徑的 代價(jià) 是這條路徑里的 最大跳躍長(zhǎng)度 。
請(qǐng)你返回這只青蛙的 最小代價(jià) 。
思路1
題目中描述的是：
一只青蛙一開(kāi)始在第一塊石頭上，它想到達(dá)最后一塊石頭，然后回到第一塊石頭。同時(shí)每塊石頭至多到達(dá)一次。
我的想法是：先將問(wèn)題轉(zhuǎn)化。將題目中這只青蛙的回程（即從最后一塊石頭返回第一塊石頭的路徑）反向，看成是第二只青蛙從第一塊石頭跳到最后一塊石頭。這樣問(wèn)題就變成：
有兩只青蛙一開(kāi)始都在第一塊石頭，它們都需要到達(dá)最后一塊石頭，同時(shí)每塊石頭至多到到達(dá)一次，求這兩只青蛙的最大跳躍長(zhǎng)度。
接下來(lái)采用 貪心策略，讓這兩只青蛙從第一塊石頭跳到最后一塊石頭。假設(shè)有 n 塊石頭，考慮一般性，我們不妨假設(shè) n >= 3，接下來(lái)我們不妨先按 n 的奇偶性分別來(lái)模擬一下：
首先，我們不妨讓第一只青蛙先跳，第二只青蛙后跳，兩只青蛙交替著跳。
當(dāng) n 為奇數(shù)時(shí)，不妨設(shè) n = 5，[0 1 2 3 4]：
第一只青蛙第 1 步：0 -> 1
第二只青蛙第 1 步：0 -> 2
第一只青蛙第 2 步：1 -> 3
第二只青蛙第 2 步：2 -> 4，第二只青蛙到達(dá)最后一塊石頭，停止。
第一只青蛙第 3 步：3 -> 4，第一只青蛙到達(dá)最后一塊石頭，停止。
最后，
第一只青蛙跳過(guò)的路徑為：0 -> 1 -> 3 -> 4
第二只青蛙跳過(guò)的路徑為：0 -> 2 -> 4
然后我們求兩只青蛙的最大跳躍長(zhǎng)度。觀察兩只青蛙跳過(guò)的路徑，不難發(fā)現(xiàn)，第二只青蛙的第一跳 0 -> 2 跨越了第一只青蛙的第一跳 0 -> 1，第二只青蛙的最后一跳 2 -> 4 跨越了第一只青蛙的最后一跳 3 -> 4，所以第一只青蛙的第一跳 1 -> 2 和最后一跳 3 -> 4 不可能是最大跳躍。也就是說(shuō)我們只需要求 0 -> 2，1 -> 3, 2 -> 4 這三跳的的最大長(zhǎng)度即可，即：
ans = max(stones[2] - stones[0], stones[3] - stones[1], stones[4] - stones[2])
寫成代碼就是：
ans = 0
for i in range(2, n):
ans = max(ans, stones[i] - stones[i - 2])
當(dāng) n 為偶數(shù)時(shí)，不妨設(shè) n = 6，[0 1 2 3 4 5]：
第一只青蛙第 1 步：0 -> 1
第二只青蛙第 1 步：0 -> 2
第一只青蛙第 2 步：1 -> 3
第二只青蛙第 2 步：2 -> 4
第一只青蛙第 3 步：3 -> 5，第一只青蛙到達(dá)最后一塊石頭，停止。
第二只青蛙第 3 步：4 -> 5，第二只青蛙到達(dá)最后一塊石頭，停止。
最后，
第一只青蛙跳過(guò)的路徑為：0 -> 1 -> 3 -> 5
第二只青蛙跳過(guò)的路徑為：0 -> 2 -> 4 -> 5
然后我們求兩只青蛙的最大跳躍長(zhǎng)度。觀察兩只青蛙跳過(guò)的路徑，不難發(fā)現(xiàn)，第二只青蛙的第一跳 0 -> 2 跨越了第一只青蛙的第一跳 0 -> 1，第一只青蛙的最后一跳 3 -> 5 跨越了第二只青蛙的最后一跳 4 -> 5，所以第一只青蛙的第一跳 1 -> 2 和第二只青蛙的最后一跳 4 -> 5 不可能是最大跳躍。也就是說(shuō)我們只需要求 0 -> 2，1 -> 3, 2 -> 4, 3 -> 5 這四跳的的最大長(zhǎng)度即可，即：
ans = max(stones[2] - stones[0], stones[3] - stones[1], stones[4] - stones[2], stones[5] - stones[3])
寫成代碼就是：
ans = 0
for i in range(2, n):
ans = max(ans, stones[i] - stones[i - 2])
綜上所述，當(dāng) n >= 3 時(shí)，求最大跳躍長(zhǎng)度的代碼有：
ans = 0
for i in range(2, n):
ans = max(ans, stones[i] - stones[i - 2])
最后，當(dāng) n == 2 時(shí)，兩只青蛙只需一跳就能從第一塊石頭跳到最后一塊石頭，最大跳躍長(zhǎng)度就是 stones[1] - stones[0]~
于是，我們有求最大跳躍長(zhǎng)度的完整代碼如下：
class Solution:
def maxJump(self, stones: List[int]) -> int:
n = len(stones)
if n == 2:
return stones[1] - stones[0]
ans = 0
for i in range(2, n):
ans = max(ans, stones[i] - stones[i - 2])
return ans
最后，我們將 ans 初始化為 stones[1] - stones[0]，就不需要將 n == 2 的情況單獨(dú)拿出來(lái)了~
class Solution:
def maxJump(self, stones: List[int]) -> int:
n = len(stones)
ans = stones[1] - stones[0]
for i in range(2, n):
ans = max(ans, stones[i] - stones[i - 2])
return ans
思路2
答案
class Solution {
public int maxJump(int[] stones) {
int result = 0;
if(stones.length==2){
result = stones[1]-stones[0];
}else {
for (int i = 2; i < stones.length; i++) {
result = Math.max(result,(stones[i]-stones[i-2]));
}
}
return result;
}
}
青蛙過(guò)河2
一只青蛙想要過(guò)河。 假定河流被等分為若干個(gè)單元格，并且在每一個(gè)單元格內(nèi)都有可能放有一塊石子（也有可能沒(méi)有）。 青蛙可以跳上石子，但是不可以跳入水中。
給你石子的位置列表 stones（用單元格序號(hào) 升序 表示）， 請(qǐng)判定青蛙能否成功過(guò)河（即能否在最后一步跳至最后一塊石子上）。開(kāi)始時(shí)， 青蛙默認(rèn)已站在第一塊石子上，并可以假定它第一步只能跳躍 1 個(gè)單位（即只能從單元格 1 跳至單元格 2 ）。
如果青蛙上一步跳躍了 k 個(gè)單位，那么它接下來(lái)的跳躍距離只能選擇為 k - 1、k 或 k + 1 個(gè)單位。 另請(qǐng)注意，青蛙只能向前方（終點(diǎn)的方向）跳躍。
比較簡(jiǎn)單的動(dòng)態(tài)規(guī)劃。dp[i][k]表示能否從第i個(gè)石頭前面的任意一個(gè)石頭j用k步跳到第i個(gè)石頭，狀態(tài)轉(zhuǎn)移方程為dp[i][k]=dp[j][k-1]||dp[j][k]||dp[j][k+1],只需要判斷當(dāng)i==len-1時(shí)能否成功即可。
答案
public boolean canCross(int[] stones) {
Boolean result = false;
for (int i = 1; i < stones.length; i++) {
if (stones[i] - stones[i - 1] > i) {
return result;
}
}
boolean[][] dp = new boolean[stones.length][stones.length];
dp[0][0] = true;
for (int i = 1; i < stones.length; i++) {
for (int j = i - 1; j >= 0; j--) {
int k = stones[i] - stones[j];
if (j + 1 < k) {//最大的步都滿足不了
break;
}
dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1];
if (i == stones.length - 1 && dp[i][k]) {
return true;
}
}
}
return result;
}
買賣股票1
給定一個(gè)數(shù)組 prices ，它的第 i 個(gè)元素 prices[i] 表示一支給定股票第 i 天的價(jià)格。
你只能選擇 某一天 買入這只股票，并選擇在 未來(lái)的某一個(gè)不同的日子 賣出該股票。設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。
返回你可以從這筆交易中獲取的最大利潤(rùn)。如果你不能獲取任何利潤(rùn)，返回 0 。
示例 1：
輸入：[7,1,5,3,6,4]
輸出：5
解釋：在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出，最大利潤(rùn) = 6-1 = 5 。
注意利潤(rùn)不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買入價(jià)格；同時(shí)，你不能在買入前賣出股票。
示例 2：
輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這種情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0。
思路還是挺清晰的，還是DP思想：
記錄【今天之前買入的最小值】
計(jì)算【今天之前最小值買入，今天賣出的獲利】，也即【今天賣出的最大獲利】
比較【每天的最大獲利】，取最大值即可
public class Solution {
public int maxProfit(int[] prices) {
int result=0;
int minP = prices[0];
for (int i = 1; i < prices.length; i++) {
result = Math.max(result,prices[i]-minP);
minP = Math.min(minP,prices[i]);
}
return result;
}
}
模板方法
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][2];
dp[0][0] = -prices[0];
for(int i=1;i<n;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[n-1][1];
}
}
dp[i-1][1]是我之前賣股票賺的錢 因?yàn)橹挥幸淮钨I賣，所以就沒(méi)這個(gè)
買賣股票2
給你一個(gè)整數(shù)數(shù)組 prices ，其中 prices[i] 表示某支股票第 i 天的價(jià)格。
在每一天，你可以決定是否購(gòu)買和/或出售股票。你在任何時(shí)候 最多 只能持有 一股 股票。你也可以先購(gòu)買，然后在 同一天 出售。
返回 你能獲得的 最大 利潤(rùn) 。
示例 1：
輸入：prices = [7,1,5,3,6,4]
輸出：7
解釋：在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 5 - 1 = 4 。
隨后，在第 4 天（股票價(jià)格 = 3）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 6 - 3 = 3 。
總利潤(rùn)為 4 + 3 = 7 。
示例 2：
輸入：prices = [1,2,3,4,5]
輸出：4
解釋：在第 1 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 5 - 1 = 4 。
總利潤(rùn)為 4 。
示例 3：
輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這種情況下, 交易無(wú)法獲得正利潤(rùn)，所以不參與交易可以獲得最大利潤(rùn)，最大利潤(rùn)為 0 。
算法題（×） 腦筋急轉(zhuǎn)彎題( √ ）
掃描一遍 只要后一天比前一天大 就把這兩天的差值加一下
public class Solution {
public int maxProfit(int[] prices) {
int result=0;
for (int i = 1; i < prices.length; i++) {
if(prices[i]-prices[i-1]>0){
result+=prices[i]-prices[i-1];
}
}
return result;
}
}
買賣股票3
給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定的股票在第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。你最多可以完成 兩筆 交易。
注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買前出售掉之前的股票）。
示例 1:
輸入：prices = [3,3,5,0,0,3,1,4]
輸出：6
解釋：在第 4 天（股票價(jià)格 = 0）的時(shí)候買入，在第 6 天（股票價(jià)格 = 3）的時(shí)候賣出，這筆交易所能獲得利潤(rùn) = 3-0 = 3 。
隨后，在第 7 天（股票價(jià)格 = 1）的時(shí)候買入，在第 8 天 （股票價(jià)格 = 4）的時(shí)候賣出，這筆交易所能獲得利潤(rùn) = 4-1 = 3 。
示例 2：
輸入：prices = [1,2,3,4,5]
輸出：4
解釋：在第 1 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接連購(gòu)買股票，之后再將它們賣出。
因?yàn)檫@樣屬于同時(shí)參與了多筆交易，你必須在再次購(gòu)買前出售掉之前的股票。
示例 3：
輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這個(gè)情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0。
示例 4：
輸入：prices = [1]
輸出：0
對(duì)于任意一天考慮四個(gè)變量:
fstBuy: 在該天第一次買入股票可獲得的最大收益
fstSell: 在該天第一次賣出股票可獲得的最大收益
secBuy: 在該天第二次買入股票可獲得的最大收益
secSell: 在該天第二次賣出股票可獲得的最大收益
分別對(duì)四個(gè)變量進(jìn)行相應(yīng)的更新, 最后secSell就是最大
收益值(secSell >= fstSell)
public int maxProfit(int[] prices) {
if(prices.length==1){
return 0;
}
int mai1 = -prices[0];//第一天買進(jìn)就是虧的
int man1 = 0;
int mai2 = -prices[0] - prices[1];
int man2 = 0;
for (int i = 1; i < prices.length; i++) {
mai1 = Math.max(mai1, -prices[i]);//今天買入就虧今天這么多錢
man1 = Math.max(man1, prices[i] + mai1);//買進(jìn)的收益加上賣出的收益
mai2 = Math.max(mai2, man1 - prices[i]);
man2 = Math.max(man2, prices[i] + mai2);
}
return man2;
}
模板方法
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
if(n<=1){
return 0;
}
int k =2;
int[][] dp = new int[n][2*k];
for(int i=0;i<k;i++){
dp[0][2*i] = -prices[0];
}
for(int i=1;i<n;i++){
for(int j=0;j<k;j++){
if(j==0){
dp[i][j*2]=Math.max(dp[i-1][j*2],-prices[i]);
dp[i][j*2+1]=Math.max(dp[i-1][j*2+1],prices[i]+dp[i-1][j*2]);
}else{
dp[i][j*2]=Math.max(dp[i-1][j*2],-prices[i]+dp[i-1][(j-1)*2+1]);
dp[i][j*2+1]=Math.max(dp[i-1][j*2+1],prices[i]+dp[i-1][j*2]);
}
}
}
return dp[n-1][2*k-1];
}
}
關(guān)鍵在于至多買賣兩次，這意味著可以買賣一次，可以買賣兩次，也可以不買賣。
接來(lái)下我用動(dòng)態(tài)規(guī)劃五部曲詳細(xì)分析一下：
- 確定dp數(shù)組以及下標(biāo)的含義
一天一共就有五個(gè)狀態(tài)， - 沒(méi)有操作
- 第一次買入
- 第一次賣出
- 第二次買入
- 第二次賣出
dp[i][j]中 i表示第i天，j為 [0 - 4] 五個(gè)狀態(tài)，dp[i][j]表示第i天狀態(tài)j所剩最大現(xiàn)金。 - 確定遞推公式
需要注意：dp[i][1]，表示的是第i天，買入股票的狀態(tài)，并不是說(shuō)一定要第i天買入股票，這是很多同學(xué)容易陷入的誤區(qū)。
達(dá)到dp[i][1]狀態(tài)，有兩個(gè)具體操作：
- 操作一：第i天買入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
- 操作二：第i天沒(méi)有操作，而是沿用前一天買入的狀態(tài)，即：dp[i][1] = dp[i - 1][1]
那么dp[i][1]究竟選 dp[i-1][0] - prices[i]，還是dp[i - 1][1]呢？
一定是選最大的，所以 dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);
同理dp[i][2]也有兩個(gè)操作： - 操作一：第i天賣出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
- 操作二：第i天沒(méi)有操作，沿用前一天賣出股票的狀態(tài)，即：dp[i][2] = dp[i - 1][2]
所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])
同理可推出剩下?tīng)顟B(tài)部分：
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
- dp數(shù)組如何初始化
第0天沒(méi)有操作，這個(gè)最容易想到，就是0，即：dp[0][0] = 0;
第0天做第一次買入的操作，dp[0][1] = -prices[0];
第0天做第一次賣出的操作，這個(gè)初始值應(yīng)該是多少呢？
首先賣出的操作一定是收獲利潤(rùn)，整個(gè)股票買賣最差情況也就是沒(méi)有盈利即全程無(wú)操作現(xiàn)金為0，
從遞推公式中可以看出每次是取最大值，那么既然是收獲利潤(rùn)如果比0還小了就沒(méi)有必要收獲這個(gè)利潤(rùn)了。
所以dp[0][2] = 0;
第0天第二次買入操作，初始值應(yīng)該是多少呢？應(yīng)該不少同學(xué)疑惑，第一次還沒(méi)買入呢，怎么初始化第二次買入呢？
第二次買入依賴于第一次賣出的狀態(tài)，其實(shí)相當(dāng)于第0天第一次買入了，第一次賣出了，然后在買入一次（第二次買入），那么現(xiàn)在手頭上沒(méi)有現(xiàn)金，只要買入，現(xiàn)金就做相應(yīng)的減少。
所以第二次買入操作，初始化為：dp[0][3] = -prices[0];
同理第二次賣出初始化dp[0][4] = 0; - 確定遍歷順序
從遞歸公式其實(shí)已經(jīng)可以看出，一定是從前向后遍歷，因?yàn)閐p[i]，依靠dp[i - 1]的數(shù)值。 - 舉例推導(dǎo)dp數(shù)組
以輸入[1,2,3,4,5]為例
大家可以看到紅色框?yàn)樽詈髢纱钨u出的狀態(tài)。
現(xiàn)在最大的時(shí)候一定是賣出的狀態(tài)，而兩次賣出的狀態(tài)現(xiàn)金最大一定是最后一次賣出。
所以最終最大利潤(rùn)是dp[4][4]
以上五部都分析完了，不難寫出如下代碼：
買賣股票4
給定一個(gè)整數(shù)數(shù)組 prices ，它的第 i 個(gè)元素 prices[i] 是一支給定的股票在第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。你最多可以完成 k 筆交易。
注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買前出售掉之前的股票）。
示例 1：
輸入：k = 2, prices = [2,4,1]
輸出：2
解釋：在第 1 天 (股票價(jià)格 = 2) 的時(shí)候買入，在第 2 天 (股票價(jià)格 = 4) 的時(shí)候賣出，這筆交易所能獲得利潤(rùn) = 4-2 = 2 。
示例 2：
輸入：k = 2, prices = [3,2,6,5,0,3]
輸出：7
解釋：在第 2 天 (股票價(jià)格 = 2) 的時(shí)候買入，在第 3 天 (股票價(jià)格 = 6) 的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 6-2 = 4 。
隨后，在第 5 天 (股票價(jià)格 = 0) 的時(shí)候買入，在第 6 天 (股票價(jià)格 = 3) 的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 3-0 = 3
class Solution {
public int maxProfit(int k, int[] prices) {
//buy[i]表示買入i次股票后的利潤(rùn)
int[] buy = new int[k+1];
//sell[i]表示完成i筆交易后的利潤(rùn)
int[] sell = new int[k+1];
//初始所有都第一次買入，后面需要確定假設(shè)所有第一次買入和當(dāng)下第一次買入比較
Arrays.fill(buy,-prices[0]);
for(int i = 1;i < prices.length;i++){
//最多支持k次交易
for(int j = 1;j <= k;j++){
//買入j次后的最大利潤(rùn)為:Math.max(當(dāng)前利潤(rùn),上一筆交易的利潤(rùn)-當(dāng)天的股票價(jià)格)
buy[j] = Math.max(buy[j],sell[j-1]-prices[i]);
//完成j次交易后的最大利潤(rùn)為：Math.max(當(dāng)前利潤(rùn)，當(dāng)前利潤(rùn)+本次交易后所得的利潤(rùn))
sell[j] = Math.max(sell[j],buy[j]+prices[i]);
}
}
return sell[k];
}
}
模板方法
class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if(n<=1){
return 0;
}
int[][] dp = new int[n][2*k];
for(int i=0;i<k;i++){
dp[0][2*i] = -prices[0];
}
for(int i=1;i<n;i++){
for(int j=0;j<k;j++){
if(j==0){
dp[i][j*2]=Math.max(dp[i-1][j*2],-prices[i]);
dp[i][j*2+1]=Math.max(dp[i-1][j*2+1],prices[i]+dp[i-1][j*2]);
}else{
dp[i][j*2]=Math.max(dp[i-1][j*2],-prices[i]+dp[i-1][(j-1)*2+1]);
dp[i][j*2+1]=Math.max(dp[i-1][j*2+1],prices[i]+dp[i-1][j*2]);
}
}
}
return dp[n-1][2*k-1];
}
}
買賣股票含冷凍期
給定一個(gè)整數(shù)數(shù)組prices，其中第 prices[i] 表示第 i 天的股票價(jià)格 。
設(shè)計(jì)一個(gè)算法計(jì)算出最大利潤(rùn)。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:
賣出股票后，你無(wú)法在第二天買入股票 (即冷凍期為 1 天)。
注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買前出售掉之前的股票）。
示例 1:
輸入: prices = [1,2,3,0,2]
輸出: 3
解釋: 對(duì)應(yīng)的交易狀態(tài)為: [買入, 賣出, 冷凍期, 買入, 賣出]
示例 2:
輸入: prices = [1]
輸出: 0
public int maxProfit(int[] prices) {
if (prices.length < 1) {
return 0;
}
//由于可以無(wú)限次交易，所以只定義兩個(gè)維度，第一個(gè)維度是天數(shù)，第二個(gè)維度表示是否持有股票，0表示不持有，1表示持有，2表示過(guò)渡期
int[][] dp = new int[prices.length][3];
dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0;
for (int i = 1; i < prices.length; i++) {
//第i天不持有股票的情況有兩種
//a.第i-1天也不持有股票
//b.第i-1天是過(guò)渡期
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);
//第i天持有股票有兩種情況
//a.第i-1天也持有股票，第i天不操作，
//b.第i-1天不持有股票，在第i天買入
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
//第i天是冷凍期只有一種情況，第i-1天持有股票且賣出
dp[i][2] = dp[i - 1][1] + prices[i];
}
return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][2]);
}
方法2
這個(gè)是一套模板
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
if(n < 2) return 0;
int[][] dp = new int[n][2];
dp[0][0] = -prices[0];
dp[1][0] = Math.max(-prices[0], -prices[1]);
dp[1][1] = Math.max(0, -prices[0] + prices[1]);
for(int i=2;i<n;i++){
dp[i][0] = Math.max(dp[i-1][0],-prices[i]+dp[i-2][1]);
dp[i][1] = Math.max(dp[i-1][1],prices[i]+dp[i-1][0]);
}
return dp[n-1][1];
}
}
買賣股票含手續(xù)費(fèi)
給定一個(gè)整數(shù)數(shù)組 prices，其中 prices[i]表示第 i 天的股票價(jià)格 ；整數(shù) fee 代表了交易股票的手續(xù)費(fèi)用。
你可以無(wú)限次地完成交易，但是你每筆交易都需要付手續(xù)費(fèi)。如果你已經(jīng)購(gòu)買了一個(gè)股票，在賣出它之前你就不能再繼續(xù)購(gòu)買股票了。
返回獲得利潤(rùn)的最大值。
注意：這里的一筆交易指買入持有并賣出股票的整個(gè)過(guò)程，每筆交易你只需要為支付一次手續(xù)費(fèi)。
示例 1：
輸入：prices = [1, 3, 2, 8, 4, 9], fee = 2
輸出：8
解釋：能夠達(dá)到的最大利潤(rùn):
在此處買入 prices[0] = 1
在此處賣出 prices[3] = 8
在此處買入 prices[4] = 4
在此處賣出 prices[5] = 9
總利潤(rùn): ((8 - 1) - 2) + ((9 - 4) - 2) = 8
示例 2：
輸入：prices = [1,3,7,5,10,3], fee = 3
輸出：6
這是一道動(dòng)態(tài)規(guī)劃的題目，我們可以定義兩個(gè)狀態(tài)，buy代表當(dāng)前持有一只股票所能獲得的最大利潤(rùn)，sell代表當(dāng)前沒(méi)有持有股票所能獲得的最大利潤(rùn)。
對(duì)于每一天，我們可以選擇買入或賣出股票，或者不進(jìn)行任何操作。如果選擇買入股票，那么當(dāng)前的利潤(rùn)就是前一天賣出股票獲得的利潤(rùn)減去當(dāng)天的股票價(jià)格和手續(xù)費(fèi)；如果選擇賣出股票，那么當(dāng)前的利潤(rùn)就是前一天買入股票獲得的利潤(rùn)加上當(dāng)天的股票價(jià)格；如果不進(jìn)行任何操作，那么當(dāng)前的利潤(rùn)就是前一天的利潤(rùn)。
具體來(lái)說(shuō)，我們可以使用以下的狀態(tài)轉(zhuǎn)移方程：
buy[i] = max(buy[i-1], sell[i-1] - prices[i] - fee)
sell[i] = max(sell[i-1], buy[i-1] + prices[i])
其中，i表示當(dāng)前的天數(shù)，buy[i]代表第i天持有股票所獲得的最大利潤(rùn)，sell[i]代表第i天沒(méi)有持有股票所獲得的最大利潤(rùn)，prices[i]代表第i天的股票價(jià)格，fee代表手續(xù)費(fèi)。
最終，我們的答案就是sell[n-1]，其中n是prices數(shù)組的長(zhǎng)度。
class Solution {
public int maxProfit(int[] prices, int fee) {
if (prices.length < 1) {
return 0;
}
int[] buy = new int[prices.length];
buy[0]=-prices[0]-fee;
int[] sell = new int[prices.length];
for (int i = 1; i < prices.length; i++) {
buy[i]=Math.max(buy[i-1],sell[i-1]-prices[i]-fee);
sell[i]=Math.max(sell[i-1],buy[i-1]+prices[i]);
}
return sell[prices.length-1];
}
}
模板方法2
class Solution {
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
int[][] dp = new int[n][2];
dp[0][0] = -prices[0];
for(int i=1;i<n;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]-fee);
}
return dp[n-1][1];
}
}
