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]; } }
