动态规划-股票交易1

本文主要是介绍动态规划-股票交易1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

动态规划解题

  dp[i][k][j] 第i天  k限制交易次数 通过买卖到什么状态(有股票，或者没有股票)
        0代表没有股票 有两种可能 前一天本身没有或者是昨天拥有今天卖了
        //dp[i][0] = max(dp[i-1][0],dp[i-1][1]+price[i]); dp[0][0]  = 0
        //dp[i][1] = max(dp[i-1][1],dp[i-1][0]-price[i]);dp[0][1]=-INT_MAX

为了节约数组空间，同时只涉及到i和i-1，使用2个变量就可以解决

dpi0 = 0;//表示初始化不持有股票，利润为0

dpi1 = -INT_MAX;//初始时未交易持有股票，不可能

状态转移

  dpi0 = max(dpi0,dpi1+prices[i]);//昨天不持有 或者 昨天持有卖出股票、dpi1 = max(dpi1,-prices[i]);//昨天持有，或者 昨天不持有买入，k=0，表示还没有交易因此只能是-prices[i];

class Solution {
public:int maxProfit(vector<int>& prices) {//dp[i][k][j] 第i天  k限制交易次数 通过买卖到什么状态(有股票，或者没有股票)//0代表没有股票 有两种可能 前一天本身没有或者是昨天拥有今天卖了//dp[i][0] = max(dp[i-1][0],dp[i-1][1]+price[i]); dp[0][0]  = 0//dp[i][1] = max(dp[i-1][1],dp[i-1][0]-price[i]);dp[0][1]=-INT_MAX//k=0 不限制交易次数int dpi0 = 0;int dpi1 = -INT_MAX;//没买的时候就持有不可能for(int i=0;i<prices.size();++i){dpi0 = max(dpi0,dpi1+prices[i]);//昨天不持有 或者 昨天持有卖出股票、dpi1 = max(dpi1,-prices[i]);//昨天持有，或者 昨天不持有买入，k=0，表示还没有交易因此只能是-prices[i];}return dpi0;//因为不持有股票这时利润绝对最低}
};

这篇关于动态规划-股票交易1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---