光速网络网站,免费做企业推广的网站,成都做网站做的好的公司,网站建设前端和后端的区别目录
LeetCode:121. 买卖股票的最佳时机
暴力解法
贪心法
动态规划法
LeetCode:122.买卖股票的最佳时机II
基本思路
LeetCode: 买卖股票的最佳时机III、IV
基本思路
C代码 LeetCode:121. 买卖股票的最佳时机 力扣题目链接 文字讲解#xff1a;121. 买卖股票的最佳时…目录
LeetCode:121. 买卖股票的最佳时机
暴力解法
贪心法
动态规划法
LeetCode:122.买卖股票的最佳时机II
基本思路
LeetCode: 买卖股票的最佳时机III、IV
基本思路
C代码 LeetCode:121. 买卖股票的最佳时机 力扣题目链接 文字讲解121. 买卖股票的最佳时机 视频讲解动态规划之 LeetCode121.买卖股票的最佳时机1 暴力解法
class Solution {
public:int maxProfit(vectorint prices) {int result 0;for (int i 0; i prices.size(); i) {for (int j i 1; j prices.size(); j){result max(result, prices[j] - prices[i]);}}return result;}
}; 但是很容易看出时间复杂度为O(n^2)----超时
贪心法 因为股票就买卖一次那么贪心的想法很自然就是取最左最小值取最右最大值那么得到的差值就是最大利润。
class Solution {
public:int maxProfit(vectorint prices) {int low INT_MAX;int result 0;for (int i 0; i prices.size(); i) {low min(low, prices[i]); // 取最左最小价格result max(result, prices[i] - low); // 直接取最大区间利润}return result;}
};
动态规划法
动规五部曲分析如下
确定dp数组dp table以及下标的含义 dp[i][0]表示第i天持有股票当然也可以表示为不持有股票但如果这样设置那么在确定递推公式时连续性不明显在最佳时机III中能比较明显的体会到所得最多现金。dp[i][1]表示第i天不持有股票所得最多现金。
确定递推公式 dp[i][0]和dp[i][1]应该分开计算。 对于dp[i][0]来说存在两种情况一种是第i-1天同样持有股票另一种是第i-1天不持有股票在第i天买入此时dp[i][0] max(dp[i-1][0]dp[i-1][1] - price[i]); 同理对于dp[i][1]同样有两种情况dp[i][1] max(dp[i-1][1]dp[i-1][0] price[i]);
dp数组如何初始化 由递推公式可以看出其基础都是要从dp[0][0]和dp[0][1]推导出来的所以dp[0][0]表示第一天持有股票即第一天买入此时最大金额为-price[0]dp[0][1]表示第一天不持有股票即为初试金额0。
确定遍历顺序 从递推公式可以看出dp[i]都是由dp[i - 1]推导出来的那么一定是从前向后遍历。
举例推导dp数组 以示例1输入[7,1,5,3,6,4]为例dp数组状态如下 显然最后的结果一定是dp[5][0]和dp[5][1]中的一个结果那么应该选择哪一个呢其实仔细想想很容易得出持有股票所拥有的金额一定小于不持有股票的金额因此最后返回值为dp[5][1]。
// 版本一
class Solution {
public:int maxProfit(vectorint prices) {int len prices.size();if (len 0) return 0;vectorvectorint dp(len, vectorint(2));dp[0][0] - prices[0];dp[0][1] 0;for (int i 1; i len; i) {dp[i][0] max(dp[i - 1][0], -prices[i]);dp[i][1] max(dp[i - 1][1], prices[i] dp[i - 1][0]);}return dp[len - 1][1];}
}; 当然这样的时间复杂度和空间复杂度都是O(n)。从递推公式可以看出dp[i]只是依赖于dp[i - 1]的状态。那么我们只需要记录 当前天的dp状态和前一天的dp状态就可以了可以使用滚动数组来节省空间。
// 版本二
class Solution {
public:int maxProfit(vectorint prices) {int len prices.size();vectorvectorint dp(2, vectorint(2)); // 注意这里只开辟了一个2 * 2大小的二维数组dp[0][0] - prices[0];dp[0][1] 0;for (int i 1; i len; i) {dp[i % 2][0] max(dp[(i - 1) % 2][0], -prices[i]);dp[i % 2][1] max(dp[(i - 1) % 2][1], prices[i] dp[(i - 1) % 2][0]);}return dp[(len - 1) % 2][1];}
};
LeetCode:122.买卖股票的最佳时机II 力扣题目链接 文字讲解LeetCode:122.买卖股票的最佳时机II 视频讲解动态规划股票问题第二弹 | LeetCode122.买卖股票的最佳时机II 基本思路 和买卖股票的最佳时机的步骤基本一致不同点在于本题可以不限次数的购买股票因此递推公式需要进行改变
dp[i][0] max(dp[i-1][0],dp[i-1][1] prices[i]);
dp[i][1] max(dp[i-1][1],dp[i-1][0] - prices[i]);
class Solution {
public:int maxProfit(vectorint prices) {int len prices.size();vectorvectorint dp(len, vectorint(2, 0));dp[0][0] - prices[0];dp[0][1] 0;for (int i 1; i len; i) {dp[i][0] max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // 注意这里是和121. 买卖股票的最佳时机唯一不同的地方。dp[i][1] max(dp[i - 1][1], dp[i - 1][0] prices[i]);}return dp[len - 1][1];}
}; 当然同样为了降低空间复杂度可以采用滚动数组的方法。
// 版本二
class Solution {
public:int maxProfit(vectorint prices) {int len prices.size();vectorvectorint dp(2, vectorint(2)); // 注意这里只开辟了一个2 * 2大小的二维数组dp[0][0] - prices[0];dp[0][1] 0;for (int i 1; i len; i) {dp[i % 2][0] max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]);dp[i % 2][1] max(dp[(i - 1) % 2][1], prices[i] dp[(i - 1) % 2][0]);}return dp[(len - 1) % 2][1];}
};
LeetCode: 买卖股票的最佳时机III、IV 题目123. 买卖股票的最佳时机 III、188. 买卖股票的最佳时机 IV 文字讲解 123.买卖股票的最佳时机III、188. 买卖股票的最佳时机 IV 视频讲解动态规划股票至多买卖两次怎么求 | LeetCode123.买卖股票最佳时机III 基本思路 买卖股票的最佳时机III这个题目要求最多出手两次使所获得的利益最大化。而最佳时机IV则是引申到了n次。因此可以先通过最佳时机III进行分析。
动规五部曲分析如下
确定dp数组dp table以及下标的含义 首先如果至多出手三次那么我们就存在5种状态即dp[0][0]表示第一天第0次不持有股票即初始状态所获的最大金额即dp[0][1]表示第一天第一次持有股票即第一次买入时的状态所获的最大金额即dp[0][2]表示第一次不持有股票即第一次卖出时的状态所获的最大金额即dp[0][3]表示第一天第二次持有股票所获的最大金额即dp[0][4]表示第一天第二次不持有股票所获的最大金额。
确定递推公式 dp[i][0] dp[i-1][0]; dp[i][1] max(dp[i-1][1],dp[i-1][0] - prices[i]); dp[i][2] max(dp[i-1][2],dp[i-1][1] prices[i]); dp[i][3] max(dp[i-1][3],dp[i-1][2] - prices[i]); dp[i][4] max(dp[i-1][4],dp[i-1][3] prices[i]);
dp数组如何初始化 数组初始化为0并且dp[0][1] -prices[0];以及dp[0][3] -prices[0];
确定遍历顺序 从递归公式其实已经可以看出一定是从前向后遍历因为dp[i]依靠dp[i - 1]的数值。
举例推导dp数组 以输入[1,2,3,4,5]为例。 C代码
// 版本一
class Solution {
public:int maxProfit(vectorint prices) {if (prices.size() 0) return 0;vectorvectorint dp(prices.size(), vectorint(5, 0));dp[0][1] -prices[0];dp[0][3] -prices[0];for (int i 1; i prices.size(); i) {dp[i][0] dp[i - 1][0];dp[i][1] max(dp[i - 1][1], dp[i - 1][0] - prices[i]);dp[i][2] max(dp[i - 1][2], dp[i - 1][1] prices[i]);dp[i][3] max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] max(dp[i - 1][4], dp[i - 1][3] prices[i]);}return dp[prices.size() - 1][4];}
}; 同样可以使用滚动数组进行优化。
// 版本二
class Solution {
public:int maxProfit(vectorint prices) {if (prices.size() 0) return 0;vectorint dp(5, 0);dp[1] -prices[0];dp[3] -prices[0];for (int i 1; i prices.size(); i) {dp[1] max(dp[1], dp[0] - prices[i]);dp[2] max(dp[2], dp[1] prices[i]);dp[3] max(dp[3], dp[2] - prices[i]);dp[4] max(dp[4], dp[3] prices[i]);}return dp[4];}
};
