题目:买股票的最佳时期||
ac了
思路:
1.dp含义:第i天时能获得的最大利润为dp[i]
2.动态转移方程:dp[i] = max(dp[i - 1], dp[i - 1] + prices[i] - prices[i - 1]);
如果prices[i] - prices[i - 1] > 0,那么就在第 i - 1天买,在 i - 1 天卖,dp[i] 取第i - 1天的最大值加上在第 i - 1天买,在 i - 1 天卖所获得的新利润;
否则第 i -1 天利润买利润是负的,在i - 1天不买,dp[i]就是dp[i - 1]
3.初始化:dp[0] = 0;其余也都是0
4.遍历顺序:从前到后
5.打印dp
代码如下:
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<int> dp(prices.size() + 1, 0);
dp[0] = 0;
for(int i = 1; i < prices.size(); i++){
dp[i] = max(dp[i - 1], dp[i - 1] + prices[i] - prices[i - 1]);
}
return dp[prices.size() - 1];
}
};
题目:121.购买股票的最佳时期
尝试解答:
做出了122题,那道题可以不断买不断卖,那么感觉在此基础上稍稍改动动态转移方程就可以解出,这道题只能在一天买一天卖
1.dp含义:第 i 天时可获取的最大利润
2.动态转移方程:
3.初始化:dp[0] = 0;其余也都初始化为0
4.遍历顺序:从前到后
5.打印dp
正确思路:
用0和1来表征状态(和打家劫舍|||类似),表示持有股票和不持有股票
1.dp数组:
dp[i][0]表示当天持有股票的零利润最大值。如果当天手上还有股票,那么利润一定是负的,因为你花钱买东西了。其实股票从第一天开始一直在买,维护着一直到第i天股票的最低价,这样利润最大。
dp[i][1]表示当天不持有股票的利润最大值。如果当天手上没有股票了,那么一定是将股票卖了。不可能是因为还没买股票,所以手上没有股票(因为由上面分析的从第一天开始就在买股票)。
2.递推公式:
对于dp[i][0],手上有股票,那么就维护股票的最低价:dp[i] = max(dp[i], -1*prices[i]) 和前一天相比谁便宜买谁的。
对于dp[i][1],手上不持有股票,已经卖了。dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])。有两种选择:第一种是今天才卖(dp[i - 1][0] + prices[i])前一天买入股票的最低价加上今天卖出的价格,得到—假如是今天卖的的话所得利润;第二种是在前面的日子里已经卖了(dp[i - 1][1]),得到—假设在前面的日子里卖,会得到利润的最优解最大值。二者进行比较,取较大值为最优解。dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
到了最后一天,必然已经把股票卖了,手上必然没有股票了,所以dp[prices.size()][1]即为所求结果。
3.初始化:
根据dp含义进行初始化:
dp[0][0]:第一天有股票,那么利润一定是 - prices[0]
dp[0][1];第一天没有股票,那么利润一定是0
4.遍历顺序:从前到后
5.打印dp
代码如下:
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
dp[0][0] = -1 * prices[0];
dp[0][1] = 0;
for(int i = 1; i < prices.size(); i++){
dp[i][0] = max(dp[i - 1][0], -1 * prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
}
return dp[prices.size() - 1][1];
}
};
题目:123.买卖股票的最佳时期||| (没有完全理解)
买股票只能产生两笔交易,且要求完成了第一笔再开始第二笔,求利润最大值
思路:
1.dp数组含义:
延续上道题通过二维数组来表示当前状态(持有or不持有?第一次or第二次?)
dp[i][1] = 第一次持有
dp[i][2] = 第一次不持有
dp[i][3] = 第二次持有
dp[i][4] = 第二次不持有
2.动态转移方程:
其实不过是把121题的过程进行了两次,最不好想的地方是,要衔接好dp[i][2] = 第一次不持有和dp[i][3] = 第二次持有的这两种情况,达到第一次卖出之后再买第二次的目的。
dp[i][1] = max(dp[i - 1][1], -1 * prices[i]);
dp[i][2] = max(dp[i - 1][2], dp[i - 1][0] + 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[prices.size() - 1][4]里面
dp[0][3]怎么初始化?和dp[0][1]一样,都初始为-prices[0],可以这样理解:第一天买了马上卖,又买第二次。(想不到啊啊啊,逻辑也理不通)
3.初始化:
dp[0][1] = -prices[0];
dp[0][2] = 0;
dp[0][3] = -prices[0];
dp[0][4] = 0;
4.遍历顺序:从前到后
5.打印dp
代码如下:
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size() + 1, vector<int>(5, 0));
dp[0][1] = -1 * prices[0];
dp[0][3] = -1 * prices[0];
for(int i = 1; i < prices.size(); i++){
dp[i][1] = max(dp[i - 1][1], -1 * 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];
}
};