Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitf5dd57c

Browse files
committed
改进123, 188的Java版本代码
1 parentfb91b76 commitf5dd57c

File tree

2 files changed

+77
-50
lines changed

2 files changed

+77
-50
lines changed

‎problems/0123.买卖股票的最佳时机III.md

Lines changed: 39 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -193,35 +193,49 @@ dp[1] = max(dp[1], dp[0] - prices[i]); 如果dp[1]取dp[1]，即保持买入股
193193
Java：
194194

195195
```java
196-
classSolution {// 动态规划
196+
// 版本一
197+
classSolution {
197198
publicintmaxProfit(int[]prices) {
198-
// 可交易次数
199-
int k=2;
200-
201-
// [天数][交易次数][是否持有股票]
202-
int[][][] dp=newint[prices.length][k+1][2];
203-
204-
// badcase
205-
dp[0][0][0]=0;
206-
dp[0][0][1]=Integer.MIN_VALUE;
207-
dp[0][1][0]=0;
208-
dp[0][1][1]=-prices[0];
209-
dp[0][2][0]=0;
210-
dp[0][2][1]=Integer.MIN_VALUE;
211-
212-
for (int i=1; i< prices.length; i++) {
213-
for (int j=2; j>=1; j--) {
214-
// dp公式
215-
dp[i][j][0]=Math.max(dp[i-1][j][0], dp[i-1][j][1]+ prices[i]);
216-
dp[i][j][1]=Math.max(dp[i-1][j][1], dp[i-1][j-1][0]- prices[i]);
217-
}
199+
int len= prices.length;
200+
// 边界判断, 题目中 length >= 1, 所以可省去
201+
if (prices.length==0)return0;
202+
203+
/*
204+
* 定义 5 种状态:
205+
* 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出
206+
*/
207+
int[][] dp=newint[len][5];
208+
dp[0][1]=-prices[0];
209+
// 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润
210+
dp[0][3]=-prices[0];
211+
212+
for (int i=1; i< len; i++) {
213+
dp[i][1]=Math.max(dp[i-1][1],-prices[i]);
214+
dp[i][2]=Math.max(dp[i-1][2], dp[i][1]+ prices[i]);
215+
dp[i][3]=Math.max(dp[i-1][3], dp[i][2]- prices[i]);
216+
dp[i][4]=Math.max(dp[i-1][4], dp[i][3]+ prices[i]);
218217
}
219218

220-
int res=0;
221-
for (int i=1; i<3; i++) {
222-
res=Math.max(res, dp[prices.length-1][i][0]);
219+
return dp[len-1][4];
220+
}
221+
}
222+
223+
// 版本二: 空间优化
224+
classSolution {
225+
publicintmaxProfit(int[]prices) {
226+
int len= prices.length;
227+
int[] dp=newint[5];
228+
dp[1]=-prices[0];
229+
dp[3]=-prices[0];
230+
231+
for (int i=1; i< len; i++) {
232+
dp[1]=Math.max(dp[1], dp[0]- prices[i]);
233+
dp[2]=Math.max(dp[2], dp[1]+ prices[i]);
234+
dp[3]=Math.max(dp[3], dp[2]- prices[i]);
235+
dp[4]=Math.max(dp[4], dp[3]+ prices[i]);
223236
}
224-
return res;
237+
238+
return dp[4];
225239
}
226240
}
227241
```

‎problems/0188.买卖股票的最佳时机IV.md

Lines changed: 38 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -170,41 +170,54 @@ public:
170170
Java：
171171

172172
```java
173-
classSolution {//动态规划
173+
// 版本一: 三维 dp数组
174+
classSolution {
174175
publicintmaxProfit(intk,int[]prices) {
175-
if (prices==null|| prices.length<2|| k==0) {
176-
return0;
177-
}
178-
179-
// [天数][交易次数][是否持有股票]
180-
int[][][] dp=newint[prices.length][k+1][2];
181-
182-
// bad case
183-
dp[0][0][0]=0;
184-
dp[0][0][1]=Integer.MIN_VALUE;
185-
dp[0][1][0]=0;
186-
dp[0][1][1]=-prices[0];
187-
// dp[0][j][0] 都均为0
188-
// dp[0][j][1] 异常值都取Integer.MIN_VALUE;
189-
for (int i=2; i< k+1; i++) {
190-
dp[0][i][0]=0;
191-
dp[0][i][1]=Integer.MIN_VALUE;
176+
if (prices.length==0)return0;
177+
178+
// [天数][交易次数][是否持有股票]
179+
int len= prices.length;
180+
int[][][] dp=newint[len][k+1][2];
181+
182+
// dp数组初始化
183+
// 初始化所有的交易次数是为确保 最后结果是最多 k 次买卖的最大利润
184+
for (int i=0; i<= k; i++) {
185+
dp[0][i][1]=-prices[0];
192186
}
193187

194-
for (int i=1; i<prices.length; i++) {
195-
for (int j=k; j>=1; j--) {
196-
//dp公式
188+
for (int i=1; i<len; i++) {
189+
for (int j=1; j<= k; j++) {
190+
//dp方程, 0表示不持有/卖出, 1表示持有/买入
197191
dp[i][j][0]=Math.max(dp[i-1][j][0], dp[i-1][j][1]+ prices[i]);
198192
dp[i][j][1]=Math.max(dp[i-1][j][1], dp[i-1][j-1][0]- prices[i]);
199193
}
200194
}
195+
return dp[len-1][k][0];
196+
}
197+
}
201198

202-
int res=0;
203-
for (int i=1; i< k+1; i++) {
204-
res=Math.max(res, dp[prices.length-1][i][0]);
199+
// 版本二: 空间优化
200+
classSolution {
201+
publicintmaxProfit(intk,int[]prices) {
202+
if (prices.length==0)return0;
203+
204+
// [天数][股票状态]
205+
// 股票状态: 奇数表示第 k 次交易持有/买入, 偶数表示第 k 次交易不持有/卖出, 0 表示没有操作
206+
int len= prices.length;
207+
int[][] dp=newint[len][k*2+1];
208+
209+
// dp数组的初始化, 与版本一同理
210+
for (int i=1; i< k*2; i+=2) {
211+
dp[0][i]=-prices[0];
205212
}
206213

207-
return res;
214+
for (int i=1; i< len; i++) {
215+
for (int j=0; j< k*2-1; j+=2) {
216+
dp[i][j+1]=Math.max(dp[i-1][j+1], dp[i-1][j]- prices[i]);
217+
dp[i][j+2]=Math.max(dp[i-1][j+2], dp[i-1][j+1]+ prices[i]);
218+
}
219+
}
220+
return dp[len-1][k*2];
208221
}
209222
}
210223
```

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp