121 买卖股票的最佳时机 动态规划方法

题目

121 题

思路

在整个过程中一共有两个状态，1.持有股票，2.未持有股票，令dp[i][0]为状态1,dp[i][1]为状态2
dp[i][0],若i天持有股票,那么共有两种可能,1.前一天持有股票,可以从dp[i-1][0]的状态转移过来,2.当天持有股票,那么值为-prices[i]，由于只能买卖一次，假设了初始基金为0，所以当购买股票的时候手上的资金就变为负数了。取两者收益最大
dp[i][1],若i天未持有股票,那么共有两种可能,1.前一天也未持有股票,可以从dp[i-1][1]的状态转移过来,2.当天卖出股票,那么前一天必定持有股票,收益为dp[i-1][0]+prices[i]。取两者收益最大
最终结果必定是未持有股票收益较大,所以返回dp[i][1]列的最下面一个结果即可

代码

class Solution{public: int maxProfit(vector<int>&prices){vector<vector<int>>dp(prices.size(),vector<int>(2));// dp[i][0]持有，dp[i][1]不持有 dp[0][0]=-1* prices[0];dp[0][1]=0;for(inti=1;i<prices.size();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]);}returndp[prices.size()-1][1];}};