目录

121. 买卖股票的最佳时机

思路

暴力解法

贪心算法

动态规划

买卖股票的最佳时机

贪心算法

动态规划

122.买卖股票的最佳时机II

思路

分析递推公式

买卖股票的最佳时机II

贪心算法

动态规划

121. 买卖股票的最佳时机

题目链接：力扣

思路

暴力解法

        暴力解答会超出时长                 

贪心算法

        因为股票就买卖一次，贪心算法的想法是：取最左侧最小值，取最右侧的最大值，那么这个差值就是可以得到的最大利润

动态规划

        其实我们要做的是，就是两件事：         在什么时候买入的时候最小         在什么时候卖出的时候赚的最多

1、确定dp数组及其下标的含义

        dp[i][0] : 表示第 i 天持有股票所得最多现金的情况。一开始现金是0 ，如果买入就是负数                       这里实际意义是： 保存买入的最小数         dp[i][1]：表示第 i 天不持有股票所得最多现金                       这里实际意义是：根据当前保存的最小买入数，保存当天卖出的话可获得的最大利润

2、确定递推公式

对于持有股票dp[i][0]:

如果在 i - 1 天就持有了股票，那就不能再买了，这种状态就是dp[i - 1][0]如果要在 i 天买入，这种状态就是 -prices[i]所以这个就是代表，怎么买入才能话最少的钱，所以应该选其中的最大值 因此 ： dp[i][0] = Math.max( dp[i -1][0] , -prices[i] );

对于不持有股票dp[i][1]

如果在 i - 1天已经卖出股票了，那就保持之前的状态，就是dp[i-1][1]如果前面没有卖出过，那就试试在 i 天卖出，这种状态就是:卖出的价格 - 前面买入的最小数，因此是：prices[ i ] - dp[i - 1][0]所以这个就是代表，当天价格 - 之前获得的最小买入，保存的是获得的利润，所以应该选取其中的最大值，因此：dp[i][1] = Math.max(dp[i -1][1], prices[i] - dp[i- 1][0]);

3、初始化dp数组

        从递推公式可以看出，我们是需要对dp[0][0]和dp[0][1]进行初始化的

        dp[0][0] 表示如果在 第0天买入股票后，手中的现金为：dp[0][0] = 0 - prices[0] = -prices[0]         dp[0][1] 表示如果在 第0天卖出股票后，手中的现金为：dp[0][1] = 0

4、遍历顺序

        显然，是从前向后遍历

买卖股票的最佳时机

贪心算法

class Solution {

public int maxProfit(int[] prices) {

// 最小值

int left = Integer.MAX_VALUE;

// 结果

int result = 0;

for (int i = 0; i < prices.length; i++) {

left = Math.min(left,prices[i]);

result = Math.max(result,prices[i]-left);

}

return result;

}

}

动态规划

版本一：使用二维数组

class Solution {

public int maxProfit(int[] prices) {

// 创建dp数组

int[][] dp = new int[prices.length][2];

// 初始化dp[]数组

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],-prices[i]); // 将最小买入位保存了下来

dp[i][1] = Math.max(dp[i-1][1],prices[i] + dp[i-1][0]); // 不断获取什么时候卖出的之后最大

}

return dp[prices.length-1][1];

}

}

版本二：使用二维滚动数组

class Solution {

public int maxProfit(int[] prices) {

// 创建dp数组

int[][] dp = new int[2][2];

// 初始化dp[]数组

dp[0][0] = -prices[0];

dp[0][1] = 0;

// 进行动态推算

for (int i = 1; i < prices.length; i++) {

dp[i % 2][0] = Math.max(dp[(i-1) % 2][0],-prices[i]); // 将最小买入位保存了下来

dp[i % 2][1] = Math.max(dp[(i-1) % 2][1],prices[i] + dp[(i-1) % 2][0]); // 不断获取什么时候卖出的之后最大

}

return dp[(prices.length-1) % 2][1];

}

}

版本三：使用一维数组

class Solution {

public int maxProfit(int[] prices) {

// 创建dp数组

int[] dp = new int[2];

// dp[0]保存最小买入数

dp[0] = Integer.MAX_VALUE;

// dp[i]保存当前卖出可获得的最大利润

dp[1] = 0;

for (int i = 0; i < prices.length; i++) {

// 更新最小买入

dp[0] = Math.min(dp[0],prices[i]);

// 获取当前卖出可获取的利润

dp[1] = Math.max(dp[1],prices[i]-dp[0]);

}

return dp[1];

}

}

122.买卖股票的最佳时机II

题目链接：力扣

思路

        这道题目在贪心算法的时候做过，再使用动态规划完成，与121题目的区别是可以买卖多次，买入前必须卖出

        和121除了递推公式，其他都是一样的

分析递推公式

dp数组的含义：

dp[i][0] 表示第 i 天持有股票所得现金，就是买入股票后手中的现金dp[i][1] 表示第 i 天不持有股票所得的最多现金，就是卖出股票后手中的现金其实这两个，代表的都是手中有的现金数

怎么推导dp[i][0]:

如果第 i-1 天持有股票，表示已经买入股票了，就不能再买入了，保持前面的状态就可以，也就是：dp[i - 1][0]如果第 i-1 天没有持有股票，表示可以买入股票了，那么就买入，手中的现金就是，dp[i - 1][1] - prices[i]

怎么推导dp[i][1]:

如果第 i-1 天不持有股票了，那就不可以卖，那么就是保持现状，dp[i - 1][1]如果第 i-1 天持有股票，那就可以卖了，dp[i - 1][0] + prices[i]

买卖股票的最佳时机II

贪心算法

class Solution {

public int maxProfit(int[] prices) {

int result = 0;

for (int i = 0; i + 1 < prices.length; i++) {

int temp = prices[i + 1] - prices[i];

if (temp > 0) {

result += temp;

}

}

return result;

}

}

动态规划

版本一：使用二维数组

class Solution {

public int maxProfit(int[] prices) {

// 创建的dp[]数组

int[][] dp = new int[prices.length][2];

// 初始化dp数组

dp[0][0] = -prices[0];

dp[0][1] = 0;

// 推导dp数组

for (int i = 1; i < prices.length; i++) {

dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]); // 这里与121的区别

dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);

}

return dp[prices.length - 1][1];

}

}

版本二：使用滚动二维数组

class Solution {

public int maxProfit(int[] prices) {

// 创建的dp[]数组

int[][] dp = new int[2][2];

// 初始化dp数组

dp[0][0] = -prices[0];

dp[0][1] = 0;

// 推导dp数组

for (int i = 1; i < prices.length; i++) {

dp[i % 2][0] = Math.max(dp[(i-1) % 2][0],dp[(i-1) % 2][1]-prices[i]);

dp[i % 2][1] = Math.max(dp[(i-1) % 2][1],dp[(i-1) % 2][0]+prices[i]);

}

return dp[(prices.length - 1) % 2][1];

}

}

版本三：使用一维数组

class Solution {

public int maxProfit(int[] prices) {

// 创建的dp[]数组

int[] dp = new int[2];

// 初始化dp数组

dp[0] = Integer.MIN_VALUE; // 代表持有当前股票手中的现金

dp[1] = 0; // 代表卖出卖出股票手中的现金

// 推导dp数组

for (int i = 0; i < prices.length; i++) {

// 前一天是持有的情况

dp[0] = Math.max(dp[0],dp[1] - prices[i]);

dp[1] = Math.max(dp[1],dp[0] + prices[i]);

}

return dp[1];

}

}

查看原文