第九章 动态规划part08
股票问题是一个动态规划的系列问题，前两题并不难，第三题有难度。
121. 买卖股票的最佳时机
视频讲解：https://www.bilibili.com/video/BV1Xe4y1u77q
class Solution {
public int maxProfit(int[] prices) {
int[] res = new int[prices.length -1];
for(int i = 1; i < prices.length; i ++){
res[i -1] = prices[i] - prices[i - 1];
}
int max = 0;
int index = 0;
for(int j = 0; j < prices.length - 1; j ++){
if(res[j] > 0){
index = j;
max = res[j];
break;
}
}
int sum = 0;
for(int k = index; k < prices.length - 1; k ++){
sum += res[k];
if(sum > max) max = sum;
}
return max;
}
}
首先 if里的break没考虑到 其次没考虑到可能不是从第一个正值开始计算的
122.买卖股票的最佳时机II
视频讲解：https://www.bilibili.com/video/BV1D24y1Q7Ls
class Solution {
public int maxProfit(int[] prices) {
int[][] dp = new int[prices.length][2];
dp[0][0] = - prices[0];//持有
dp[0][1] = 0;
for(int i = 1; i < prices.length; 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], dp[i-1][0] + prices[i]);
}
return dp[prices.length -1][1];
}
}
123.买卖股票的最佳时机III
这道题一下子就难度上来了，关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。
视频讲解：https://www.bilibili.com/video/BV1WG411K7AR
class Solution {
public int maxProfit(int[] prices) {
int[][] dp = new int[prices.length][4];
dp[0][0] = - prices[0];
dp[0][1] = 0; //持有
dp[0][2] = - prices[0];
dp[0][3] = 0;
for(int i = 1; i < prices.length; i ++){
dp[i][0] = Math.max(dp[i-1][0], - prices[i]);
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);
dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1]-prices[i]);
dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] + prices[i]);
}
return dp[prices.length -1][3];
}
}
