本文主要是介绍代码随想录算法训练营day53 || 121.买卖股票的最佳时机，122.买卖股票的最佳时机||，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
视频讲解：
动态规划之 LeetCode：121.买卖股票的最佳时机1_哔哩哔哩_bilibili
动态规划，股票问题第二弹 | LeetCode：122.买卖股票的最佳时机II_哔哩哔哩_bilibili
121.买卖股票的最佳时机
思路：寻找全局最大间隔，对于不满足后大前小的地方，直接继承前一位置的状态。
// 时间复杂度O(n)
// 空间复杂度O(n)class Solution {public int maxProfit(int[] prices) {// 思路就是保存全局最大的间隔，但这个间隔是由i位置之后的内容所创造的if(prices.length == 0 || prices == null)return 0;int n = prices.length;// dp数组的含义是前i+1天所能取得的最大收益int[] dp = new int[n];int in = 0; //购入股票的下标dp[0] = 0;for(int i=1; i<n; i++){if(prices[i] < prices[in]){in = i;dp[i] = dp[i-1]; // 本来此处应该是赋值为0，表示此处为新购入}elsedp[i] = Math.max(dp[i-1], prices[i]-prices[in]);}return dp[n-1];}
}122. 买卖股票的最佳时机||
思路：二维dp在递推公式上与 买卖股票的最佳时机I 有这不同，是dp[i-1][0]-prices[i]替代-prices[i]这个过程， 其实本质就是-prices[i]表示的dp[i-1][0]总是零，即模拟出了总是第一次买入，而没有其他买入所带来的收益。而去两题针对dp[i][1]取max都是喜欢买的价格尽可能的小或者减少利润的消耗。
// 时间复杂度O(n)
// 空间复杂度O(n)和O(2n)class Solution {public int maxProfit(int[] prices) {// 使用贪心策略// int benefit = 0;// for(int i=0; i<prices.length; i++){// if(i+1<prices.length && prices[i+1] > prices[i])// benefit += prices[i+1]-prices[i];// }// return benefit;// 使用动态规划策略int n=prices.length;int[][] dp = new int[n][2];// dp[i][0] 表示不持有股票的最大收益// dp[i][1] 表示持有股票的最大收益 dp[0][0] = 0;dp[0][1] = -prices[0]; // 由于可以多次买入，所以这里可以直接赋值为-prices[0]for(int i=1; i<n; 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[n-1][0];// 时间复杂度O(n)
// 空间复杂度O(2n)// 使用动态规划策略int n=prices.length;int[][] dp = new int[n][2];// dp[i][0] 表示不持有股票的最大收益// dp[i][1] 表示持有股票的最大收益 dp[0][0] = 0;dp[0][1] = -prices[0]; // 由于可以多次买入，所以这里可以直接赋值为-prices[0]for(int i=1; i<n; 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[n-1][0];}
}这篇关于代码随想录算法训练营day53 || 121.买卖股票的最佳时机，122.买卖股票的最佳时机||的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
