自媒体平台排名前十,网站性能优化方法,东莞网站推广优化搜索推广,淘宝关键词121.买卖股票的最佳时机
思路一#xff1a;贪心
不断更新最小买入值不断更新当前值和最小买入值的差值最大值 思路二#xff1a;动态规划#xff08;今天自己写出来了哈哈哈哈哈哈哈#xff09;
1.dp存储#xff1a;dp[i][0] 表示当前持有 dp[i][1]表示当前不持有2.状…121.买卖股票的最佳时机
思路一贪心
不断更新最小买入值不断更新当前值和最小买入值的差值最大值 思路二动态规划今天自己写出来了哈哈哈哈哈哈哈
1.dp存储dp[i][0] 表示当前持有 dp[i][1]表示当前不持有2.状态转移方程递推式 dp[i][0]max ( dp [ i - 1 ] [ 0 ] , - prices [ i ] ) 之前就持有/当前买入 dp[i][1]max ( dp [ i - 1 ] [ 1 ] , dp [ i - 1 ] [ 0 ] prices [ i ] ) 之前就没持有/当前卖出3.初始化dp[0][0]-prices[0] dp[0][1] 04.遍历顺序1-n
class Solution {
public:int maxProfit(vectorint prices) {int nprices.size();vectorvectorintdp(n,vectorint(2));dp[0][0]-prices[0];dp[0][1]0;for(int i1;in;i){dp[i][0]max(dp[i-1][0],-prices[i]);dp[i][1]max(dp[i-1][1],dp[i-1][0]prices[i]);}return dp[n-1][1];//最后肯定不持有利润最大}
}; 122.买卖股票的最佳时机||拿捏
思路一贪心
只要有利润增长就卖出最后一定获得最大利润 思路二动态规划
1.dp存储dp[i][0]为持有 dp[i][1]为不持有
2.状态转移方程递推式
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 ] ) 之前没持有/现在卖出上一次持有的金额 卖出的金额
3.初始化dp[0][0]-prices[0] dp[0][1]0
4.遍历顺序1-n
class Solution {
public:int maxProfit(vectorint prices) {int nprices.size();vectorvectorintdp(n,vectorint(2));dp[0][0]-prices[0];dp[0][1]0;for(int i1;in;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]);}return dp[n-1][1];}
}; 123.买卖股票的最佳时机|||
思路动态规划5个状态
class Solution {
public:int maxProfit(vectorint prices) {int nprices.size();vectorvectorintdp(n,vectorint(5,0));dp[0][1]-prices[0];dp[0][3]-prices[0];for(int i1;in;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[n-1][4];}
};
