買賣股票最佳時機2

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <vector>
 4 using namespace std;
 5 
 6 
 7 
 8 /*
 9 dp[i][0] 表示第i天持有股票所得最多現金，
10 dp[i][1] 表示第i天不持有股票所得最多現金
11 
12 如果第i天持有股票即dp[i][0]， 那么可以由兩個狀態推出來
13 (1) 第i-1天就持有股票，那么就保持現狀，所得現金就是昨天持有股票的所得現金 即：dp[i - 1][0]
14 (2) 第i天買入股票，所得現金就是買入今天的股票后所得現金即：-prices[i]，
15 為什么這里是 -price[i] ?  既然第i天買入，由于題目要求只能買賣一次，那么說明前面第i-1天
16 就沒有買過股票，那么前面的第i-1天現金沒有任何變動，此時第i天買入股票，那么就是要付出一筆價格為
17 price[i]的錢，所以付出了錢，所得現金就是 -price[0]，我們這里只在乎現金的變動，變動！
18 那么dp[i][0]應該選所得現金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);
19 
20 如果第i天不持有股票即dp[i][1]， 也可以由兩個狀態推出來
21 (1) 第i-1天就不持有股票，那么就保持現狀，所得現金就是昨天不持有股票的所得現金 即：dp[i - 1][1]
22 (2) 第i天賣出股票，所得現金就是按照今天股票價格賣出后所得現金即：prices[i] + dp[i - 1][0]，
23 同樣，我們也只在乎現金的變動，第i天賣出股票，說明前面不知道哪天有買入過股票，那么前面的現金有過
24 變動，所以這里不能只計算賣出的股票所得的現金 prices[i]，還得再算上前面不知道哪天買入股票后所計算
25 出來的所得現金，這個現金累計可以累計到i-1天上，所以還要再加上第i-1天持有這支股票的所得現金dp[i - 1][0]
26 同樣，我們這里只在乎現金的變動，變動！
27 同樣dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
28 */
29 
30 /*   開辟一個 len*2 的二維數組，有len行2列，之所以有2列，是因為
31 dp[i][0] 表示第i天持有股票所得最多現金，
32 dp[i][1] 表示第i天不持有股票所得最多現金
33 這里只有持有和不持有兩種狀態
34 */
35 //dp 2
36 int MaxProfitmore(vector<int>& stocks){
37     int length = stocks.size();
38     vector<vector<int>> dp(length,vector<int> (2));
39     dp[0][0] = -stocks[0];
40     dp[0][1] = 0;
41     for(int i = 1;i < length;i++){
42         dp[i][0] = max(dp[i-1][0],dp[i-1][1]-stocks[i]);
43         dp[i][1] = max(dp[i-1][1], stocks[i]+dp[i-1][0]);
44     }    
45     //為什么返回dp[i][1]這個狀態，而不是dp[i][0]?因為不持有股票狀態所得的金錢一定比持有股票所得的金錢得到的多
46     return dp[length-1][1];
47 }
48 int main(void){
49     vector<int> stocks = {7,1,5,3,6,4};
50     printf("最大利潤:%d\n",MaxProfitmore(stocks));
51     return 0;
52 }