核心还是状态转移，只要搞清每个状态是什么就非常简单
搞不清楚转移过程可以打表看看

这里从dp[i][j],i从1开始是因为习惯性想避开i-1导致越界

1

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

剑指 Offer 63. 股票的最大利润

买卖该股票一次可能获得的最大利润是多少？

解析：

这两个是同一道题，都是只能买一次卖一次
下面两种方法只是思考角度不同：
1.dp[i][0]和dp[i][1]分别代表无股票（可能是没买，可能是卖了）、有股票（只能买一次，所以不能叠加上次值）两种状态
%2是个节省空间的方法，可以不加
2.
dp[i][0]未买过
dp[i][1]买过一次，且未卖出
dp[i][2]买过一次，且卖出

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len=prices.size();
        vector<vector<int>>dp(2,vector<int>(2,0));
        int ans=0;
        dp[1][0]=0;
        dp[1][1]=-prices[0];
        for(int i=2;i<=len;i++){
            dp[i%2][0]=max(dp[(i-1)%2][0],dp[(i-1)%2][1]+prices[i-1]);
            dp[i%2][1]=max(dp[(i-1)%2][1],-prices[i-1]);

            
        }
        return dp[len%2][0];

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len=prices.size();
        if(len==0)return 0;
        vector<vector<int>>dp(len+1,vector<int>(3,0));
        dp[1][1]=-prices[0];
        for(int i=2;i<=len;i++){
            dp[i][0]=dp[i-1][0];
            dp[i][1]=max(dp[i-1][0]-prices[i-1],dp[i-1][1]);
            dp[i][2]=max(dp[i-1][1]+prices[i-1],dp[i-1][2]);
        }
        return dp[len][2];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2

122. 买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

解析：

和1相比，可以多次买入卖出，意思就是买入可以叠加上次状态了

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len=prices.size();
        vector<vector<int>>dp(len+1,vector<int>(2,0));
        dp[1][1]=-prices[0];
        dp[1][0]=0;
        for(int i=2;i<=len;i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i-1]);
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i-1]);
            
        }
        return dp[len][0];
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3

123. 买卖股票的最佳时机 III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

解析：

和2相比，限制买入次数，只能买入两次
就用5个状态标记
dp[i][0] 未买过
dp[i][1] 买过一次，并持有
dp[i][2] 买过一次，并卖了
dp[i][3]买过两次，并持有
dp[i][4]买过两次，并卖了

注意初始化，可以一天买了又卖又买

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len=prices.size();
        vector<vector<int>>dp(len+1,vector<int>(5,0));
        
        dp[1][1]=-prices[0];
        //注意一天可以买卖两次
        dp[1][3]=-prices[0];
        for(int i=2;i<=len;i++){
            dp[i][0]=dp[i-1][0];
            dp[i][1]=max(dp[i-1][0]-prices[i-1],dp[i-1][1]);
            dp[i][2]=max(dp[i-1][1]+prices[i-1],dp[i-1][2]);
            dp[i][3]=max(dp[i-1][2]-prices[i-1],dp[i-1][3]);
            dp[i][4]=max(dp[i-1][3]+prices[i-1],dp[i-1][4]);
            


        }
        return dp[len][4];


    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

4

188. 买卖股票的最佳时机 IV

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）

解析：

和3相比，买入两次变k次
就用2k+1个状态标记
dp[i][0] 未买过
dp[2i+1][1] 买过一次，并持有
dp[ik+2][2] 买过一次，并卖了
然后一循环就完了

注意初始化，可以一天买了又卖又买又…

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int len=prices.size();
        if(len==0)return 0;
        vector<vector<int>>dp(len+1,vector<int>(2*k+1,0));
        for(int i=0;i<k;i++){
            dp[1][2*i+1]=-prices[0];
        }
        for(int i=2;i<=len;i++){
            dp[i][0]=dp[i-1][0];
      
            for(int j=0;j<k;j++){
                dp[i][2*j+1]=max(dp[i-1][2*j]-prices[i-1],dp[i-1][2*j+1]);
                dp[i][2*j+2]=max(dp[i-1][2*j+1]+prices[i-1],dp[i-1][2*j+2]);
            }
        }
        return dp[len][2*k];
       
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

5

714. 买卖股票的最佳时机含手续费

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

解析：

跟2相比，在卖出时-fee就行

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int len=prices.size();
        vector<vector<int>>dp(len+1,vector<int>(2,0));
        dp[1][1]=-prices[0];
        for(int i=2;i<=len;i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i-1]-fee);
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i-1]);
        }
        return dp[len][0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13