05 August 2008
跟II只有些微区别
dp[i][0] 表示第 i 天不持有可获得的最大利润；
dp[i][1] 表示第 i 天持有可获得的最大利润（注意是第 i 天持有，而不是第 i 天买入）。
不持有：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)
对于今天不持有，可以从两个状态转移过来：1. 昨天也不持有；2. 昨天持有，今天卖出。两者取较大值。
持有：dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
对于今天持有，可以从两个状态转移过来：1. 昨天也持有；2. 昨天不持有，今天买入。两者取较大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int maxProfit(int[] prices, int fee) {
int len = prices.length;
int[][] dp = new int[len][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[len - 1][0];
}
}
状态压缩
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int maxProfit(int[] prices, int fee) {
int len = prices.length;
int[] dp = new int[2];
dp[0] = 0;
dp[1] = -prices[0];
for (int i = 1; i < len; i++) {
int tmp = dp[0];
dp[0] = Math.max(dp[0], dp[1] + prices[i] - fee);
dp[1] = Math.max(dp[1], tmp - prices[i]);
}
return dp[0];
}
}