题解 | #买卖股票的最好时机(二)#
买卖股票的最好时机(二)
https://www.nowcoder.com/practice/9e5e3c2603064829b0a0bbfca10594e9
2022.0818算法第37题买卖股票的最好时机(二)
这个也可以使用动态规划求解。
这个状态矩阵也是没想到，看了解析才知道采用二维数组
1、状态矩阵
定义状态 dp[i][0] 表示第 i 天交易完后手里没有股票的最大利润，
dp[i][1] 表示第 i 天交易完后手里持有一支股票的最大利润。
vector<vector<int>> dp(prices.size(),vector<int>(2,0));
2、初始值
dp[0][0]=0; dp[0][1]=-prices[0];3、状态转移方程
for(int i=1;i<prices.size();i++){
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]);
}
这个问题也可以换个算法，直接对问题进行分析
直接对每个利润进行相加，最后获取最大的利润
int max_p=0;
for(int i=1;i<prices.size();i++){
if(prices[i]>prices[i-1]){
max_p+=(prices[i]-prices[i-1]);
}
}
return max_p;
这个更加简单一点，但是这个应该属于贪心算法，这个还没接触，还要继续学习。
CVTE公司福利 258人发布
