动态规划系列之：股票买卖问题!1_注意先买入才能卖出 算法

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

题目：
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例1：

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
1
2
3
4

思路：
　　　后面的题目都是针对动态规划，先拿这道小题目拿拿味！
　　　这一题看起来比较简单，只需要买卖１次，看利润最大，其实就是求差值最大解，如果数组是递减的,无解返回0.那我可以对每个位置进行判断。判断在这个位置卖出获得的最大利润是多少，遍历所有位置，取最大值。而某个位置的最大利润就是这个位置的值减去倒他前面为止的股票最低值！ 这个过程可以不断的迭代更新，最大和最小的过程。

代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
    int maxmoney=0;
    int minmoney=INT_MAX;
    int n=prices.size();
    //我在卖的时候看下我前面的最小值。然后利润就是X-min
    for(int i=0;i<n;i++){
       maxmoney=max(maxmoney,prices[i]-minmoney);
       minmoney=min(minmoney,prices[i]);
    }
    return maxmoney;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

121.买卖股票的最佳时机
题目：
　　　给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

思路：
　　　用暴力发会超时，想想看还有什么方法。注意到利润的计算一定是在第二个元素才开始的至少！因为得先买入。所以我们可以从第二个元素开始计算当前的pirce减去之前元素的最小值。，代表了在这个价位卖出去能获得的最大利润，然后和max利润进行比较，如果大了，就替代！还有个就是最大利润如果是负数肯定不要，那就给0，所以初始最大利润肯定是0，这样就不会低于0. 一旦涉及到最大最小值的变换，一定要设初值。同样最小值的初值，为了让第一个元素能选到，min一开始要尽可能大！

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int inf = 1e9;
        int minprice = inf, maxprofit = 0;
        for (int price: prices) {
            maxprofit = max(maxprofit, price - minprice);
            minprice =  min(price, minprice);
        }
        return maxprofit;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13

122. 买卖股票的最佳时机 II
题目：
　　给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。　
思路：
　　 用动态规划的思想来解决问题，善于将题目描述成语言，即将复杂的题目量化指标。每天就是有股票和没股票两个状态。然后可能是前一天和今天一样或者今天做了操作改变了！根据这个就可以写出动态规划方程求解：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
    int n=prices.size();
    vector<vector<int>>dp(n,vector<int>(2)); //核心在于找状态，要善于将题目的变量描述成语言。
    dp[0][1]=-prices[0];
    dp[0][0]=0;
    for(int i=1;i<n;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][0];
    }
};
// 思考下状态的独立性，或者最有结构为什么成立！ 因为我们分析了每个位置在有和没有的所有情况的最优解
//实际的操作中获得的利润其实也是和前面一次有关系无非是上一次有股票我现在卖还是不卖，上一次没股票我是买还是不买。这个关系肯定是独立地。
//然后就是分析为什么利润最大值是独立的。注意到我们分析的不是单纯的某个位置利润最大值。而是
//某个位置是否有股票的情况下利润的最大值。
//注意到状态转移方程中每次01最多2个状态，我为什么要取max呢，我完全可以取小的。但是注意到取了小的
//是否能保证之后更大呢！ 并不是，因为你发现每次的值之和上次有关系最终会很小。这个很难理清楚大概就是这样
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

123. 买卖股票的最佳时机 III
题目：
　　　给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路：
　　　这道题和之前的题目差不多，但是增加了限制条件，最多参与2笔交易。那意味着我们的状态方程又多了一维度变量，即交易满0笔 1笔和2笔！ 注意到满2笔之后还持有股票的话是不存在的。对不存在的解，我们不选择就好了 考虑到我们的问题是求max，那样就可以用很小的数字来滤掉这个解。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
    //同样用动态规划，感觉要用三维的，第三维表示卖出去1次，卖出去2次
    int n=prices.size();
    int dp[n][2][3];
    dp[0][0][0]=0;dp[0][1][0]=-prices[0];
    //初始条件本来6个情况，剩下4个是无解。
    dp[0][0][1] = dp[0][1][1] = -1e6;//不可能
    dp[0][0][2] = dp[0][1][2] = -1e6;//不可能
    for(int i=1;i<n;i++){
        dp[i][0][0]=0;            
        dp[i][0][1]=max(dp[i-1][0][1],dp[i-1][1][0]+prices[i]); 
        dp[i][0][2]=max(dp[i-1][0][2],dp[i-1][1][1]+prices[i]);            
        dp[i][1][0]=max(dp[i-1][1][0],dp[i-1][0][0]-prices[i]);               
        dp[i][1][1]=max(dp[i-1][1][1],dp[i-1][0][1]-prices[i]);               
        dp[i][1][2]=-1e6;               
    }
        int max1= max(dp[n-1][0][1],dp[n-1][0][2]);
        return max(max1,0);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

188. 买卖股票的最佳时机 IV
题目：
　给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
　设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
　注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路：
　　这道题我真是做吐了！其实和买卖股票问题3很相像，但是我每次都测试失败！到最后看了评论，有个人用java的思路，和我的差不多，但是他是计算到i天有无持股最多允许k次交易时的最大利润！ 而且是买入算是一次交易，但是我就算复制它的代码，放到我这还是失败 无语子。。。
　　最终发现就是在C++中我直接定义一个三维数组，并不是所有元素默认是0，我随机查看某些元素，竟然达到了144，3w多。。。所以我在操作前对他们进行了置0处理！
　　其次数组长度小于2无法完成交易，要给他0; 考虑到完成一次完整的交易需要2天，如果交易的次数大于天数的一半，就没有交易的必要了，比如5天其实最多只能完成2次交易，所以k应该取交易天数一半和他本身的最小值。
　　然后我们要进行覆初值。注意到我们的程序看起来很复杂，但是分开考虑就是对状态0和状态1分别在不同的交易次数下进行处理。初始在第一个位置操作。对不可能实现的操作我给很小的值，在最后的比较中将不考虑他们。
　　在主循环中考虑到当k=0和当k=最后一个值的特殊情况，我们将他们单独拉出来处理处理即可。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
    int n=prices.size();
    if(n<2)
    return 0;
    if(k==0)
    return 0;
    int kk=min(n/2,k);
    int dp[n][2][kk+1];
      for(int i=0;i<n;i++){
        for(int j=0;j<2;j++){
            for(int z=0; z<=kk;z++)
             dp[i][j][z]=0;
        }
    }


    dp[0][0][0]=0;dp[0][1][0]=-prices[0];
    for(int i=1; i<=kk;i++){
        dp[0][0][i]=-1e6;//不可能
        dp[0][1][i]=-1e6;//不可能
    }
    for(int i=1;i<n;i++){
        dp[i][0][0]=0;
        dp[i][1][0]=max(dp[i-1][1][0],dp[i-1][0][0]-prices[i]);     
        for(int j=1; j<k;j++){
           dp[i][0][j]=max(dp[i-1][0][j],dp[i-1][1][j-1]+prices[i]); 
           dp[i][1][j]=max(dp[i-1][1][j],dp[i-1][0][j]-prices[i]); 
        }         
        dp[i][0][kk]=max(dp[i-1][0][kk],dp[i-1][1][kk-1]+prices[i]);        
        dp[i][1][kk]=-1e6;          
    } 
        int max1=0;
        for(int i=1; i<=kk;i++){
            max1=max(max1,dp[n-1][0][i]);
        }
        return max1;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

好，现在换种方法，试下我们那啥 就是 计算到i天有无持股最多允许k次交易时的最大利润！
之前测试失败就是初值，就是前面的条件 dp不是要写前面的条件么，一直没给他写好，这会补充上了，终于成功了。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
    int n=prices.size();
    if(n<2)
    return 0;
    int K=min(n/2,k);
    int dp[n][2][K+1];
    for(int i=0;i<n;i++){
        for(int j=0;j<2;j++){
            for(int z=0; z<=K;z++)
             dp[i][j][z]=0;
        }
    }
    
    for(int i=0; i<=K;i++){
        dp[0][0][i]=0;//不可能
        dp[0][1][i]=-prices[0];//不可能
    }
    for(int i=1;i<n;i++){
           dp[i][0][0]=0;
           dp[i][1][0]=max(dp[i-1][1][0],dp[i-1][0][0]-prices[i]); 
        for(int j=1; j<=K;j++){
           dp[i][0][j]=max(dp[i-1][0][j],dp[i-1][1][j-1]+prices[i]); 
           dp[i][1][j]=max(dp[i-1][1][j],dp[i-1][0][j]-prices[i]); 
        } 
    } 
        return dp[n-1][0][K];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

309. 最佳买卖股票时机含冷冻期
题目：
　　给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​
　　设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

思路：
　　　股票买卖真的卖出花来了。。这道题目拿到手就知道多了个一状态就是冷冻期，然而第一次写代码的时候出错了。
　　　注意到我们的状态都是当前结束后的状态，即卖或者买都是当天操作结束之后存在的状态。dp[i][0] 表示第i天操作完成之后没有股票且不在冷冻期的最大收益，dp[i][1] 表示第i天操作完成之后有股票的最大收益，dp[i][2] 表示第i天操作完成之后没有股票且处在冷冻期的收益。
　　　注意到dp[i][2] 意味着当前操作后处在冷冻期，说明今天卖货了，肯定是前一天有货的状态下转移来的！ 类似这样分析3个状态才能得到正确解。包括dp[i][0] 来自前一天也是没股票或者前一天结束之后是冷冻期。因为我当天虽然是冷冻期，但是我结束之后的状态 之后！ 之后不是冷冻期。这个和之前的2个状态有点不同。
　　 1 2 3 0 2
　 dp[1] dp[2] dp[0] dp[1] dp[2]

class Solution {
public:
    int maxProfit(vector<int>& prices) {
    //增加了一个冷冻期 变成3天1个周期了
    //状态变成3个了 持有股票 没持有股票， 冷冻期
    int n=prices.size();
    
    vector<vector<int>>dp(n,vector<int>(3));
    dp[0][0]=0;dp[0][1]=-prices[0];dp[0][2]=0;
    for(int i=1; i<n; i++){
        dp[i][0]=max(dp[i-1][0],dp[i-1][2]);
        dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
        dp[i][2]=dp[i-1][1]+prices[i];
    }
      return max(dp[n-1][0],dp[n-1][2]);
    }
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

最后，注意到股票问题的3维动态规划似乎存在更好的解，在Leetocde解答专区，有空去看看他们到底怎么求解的！！