买股票

DawninShadow 2020-01-09 PM 551℃ 0条

不得不说,人家的博客写的太好了,真是有种看武林秘籍的感觉

动态规范问题三要素:

  • DP方程

三种状态,天数,买卖次数,当前是否持有股票
DPday[true]
DPday[false]

  • 迁移方程

不操作,或者卖出 或者 买入
DPday[True] = Math.max(DPday-1[True],DPday-1[False] - prices[Daynow])
DPday[False] = Math.max(DPday-1[False],DPday-1[True] + prices[Daynow])

  • 初始状态

对于Day = 0 ;收益一定为0
对于Day = 0 ; num = 1;不合法;
对于Day = 0; True不合法;

121. 买卖股票的最佳时机
只允许交易一次,所以num为定值1,带入方程
DPday[1] = Math.max(DPday-1[1],DPday-1[0] - prices[Daynow])
DPday[False] = Math.max(DPday-1[False],DPday-1[1] + prices[Daynow])
对于DPday-1[0],意义为前day-1天,进行了0次交易,没持有股票的情况.很明显值肯定为 0
所以有程序:

var maxProfit = function(prices) {
    var dp = Array.from(new Array(prices.length),()=>[])
    dp[0][0] = [0];
    dp[0][1] = - prices[0]
    for (var i = 1; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i-1][1],  -prices[i]);
    }
    return dp[prices.length-1][0]; 
};

dpi-1 和 dpi-1 和 已知条件prices[i-1] —> dpi
dpi-1 和 已知条件prices[i-1] —> dpi
所以就没必要通过数组存储两个变量存前置状态即可,加上特判代码如下:

var maxProfit = function(prices) {
    if(prices.length == 0){
        return 0
    }
    var dp_num_F = 0;
    var dp_num_T = - prices[0]
    for (var i = 0; i < prices.length; i++) {
        dp_num_F = Math.max(dp_num_F, dp_num_T + prices[i]);
        dp_num_T = Math.max(dp_num_T,  -prices[i]);
    }
   return dp_num_F ;  
};

122. 买卖股票的最佳时机 II
允许多次交易,num为无限,带入方程
跟上一题的区别就在于DPday-1[0],变成了DPday-1[0],之前可以进行任意次交易,那在计算收益的时候把之前的收益加上即可

var maxProfit = function(prices) {
    if(prices.length == 0){
        return 0
    }
    var dp_num_F = 0;
    var dp_num_T = - prices[0]
    for (var i = 0; i < prices.length; i++) {
        dp_num_F = Math.max(dp_num_F, dp_num_T + prices[i]);
        dp_num_T = Math.max(dp_num_T,  dp_num_F -prices[i]);
    }
   return dp_num_F ;  
};

123. 买卖股票的最佳时机 III
对于此题DP方程为三维的,拆分成DP_T和DP_F两个二维数组更方便管理
次题num为2;理论上应该再引入一个循环去处理num,但因为就循环两次,所以直接写两遍逻辑也可以

    var maxProfit = function(prices) {
           if(prices.length <= 1){
                return 0
            }
        var DP_T = Array.from(new Array(prices.length+1),()=>[]);//天数和购买次数
        var DP_F = Array.from(new Array(prices.length+1),()=>[]);
        DP_F[0][0] = 0; //没持有股票
        DP_T[0][0] = -prices[0];//第一天就买了
        DP_F[0][1] = 0;//第一天就买了又买了
        DP_T[0][1] = -prices[0];//第一天买了又卖了又买了
        for(var i = 1;i<=prices.length;i++){
            //DP为现在有的收益,对于没持有股票的时候就是净收益,持有股票的时候为 收益-本金

            DP_F[i][0] = Math.max(DP_F[i-1][0],DP_T[i-1][0] + prices[i-1] )
            //不操作或者,把第一次买的股票今天卖掉

            DP_T[i][0] = Math.max(DP_T[i-1][0], - prices[i-1])
            //不操作或者,买入一只股票

            DP_F[i][1] = Math.max(DP_F[i-1][1],DP_T[i-1][1] + prices[i-1] )
            //不操作或者,或者把买入的股票卖掉

            DP_T[i][1] = Math.max(DP_T[i-1][1],DP_F[i-1][0] - prices[i-1] )
            //不操作或者,或者在原有收益的基础上买入股票
        }
        return DP_F[prices.length][1]
};

同理我们可以进行优化,抛弃DP数组存储:

    var maxProfit = function(prices) {
        if( 1 >= prices.length){return 0}
        var  DP_F_Zero = DP_F_One = 0; 
        var  DP_T_Zero = DP_T_One  = -prices[0];
        for(var i = 1;prices.length>=i;i++){
            DP_F_Zero = Math.max(DP_F_Zero, DP_T_Zero + prices[i-1] )
            DP_T_Zero  = Math.max(DP_T_Zero , -prices[i-1] )
            DP_F_One = Math.max( DP_F_One,DP_T_One + prices[i-1] )
            DP_T_One = Math.max(DP_T_One,DP_F_Zero - prices[i-1] )
        }
        return DP_F_One
};

309. 最佳买卖股票时机含冷冻期
跟第二题唯一的区别就是一个是__DP_F[i-1]__ ,一个是__DP_F[i-2]__

var maxProfit = function(prices) {
    if(prices.length <= 1){return 0 }
    var DP_T = [-prices[0]]
    var DP_F = [0]
    for (var i = 1; i < prices.length; i++) {
        if(1 == i){
            DP_F[i] = Math.max(DP_F[i-1], DP_T[i-1] + prices[i]);
            DP_T[i] = Math.max(DP_T[i-1],  -prices[i]);
        }else{
            DP_F[i] = Math.max(DP_F[i-1], DP_T[i-1] + prices[i]);
            DP_T[i] = Math.max(DP_T[i-1], DP_F[i-2] - prices[i]);
        }
    }
    return  DP_F[prices.length-1]; 
};

714. 买卖股票的最佳时机含手续费
第二题的变种.每次买入的时候减个手续费就行

var maxProfit = function(prices, fee) {
        if(prices.length == 0){
        return 0
    }
    var dp_num_F = 0;
    var dp_num_T = - prices[0] - fee
    for (var i = 0; i < prices.length; i++) {
        dp_num_F = Math.max(dp_num_F, dp_num_T + prices[i]);
        dp_num_T = Math.max(dp_num_T,  dp_num_F - prices[i]-fee);
    }
   return dp_num_F ; 
};

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

按照第三题的思路加入一个循环处理购买次数即可:
但是这样写的话会导致内存爆炸.JS好弱啊Orz

        var maxProfit = function(k, prices) {
       
       if(prices.length <= 1){
            return 0
        }

    var DP_T = Array.from(new Array(prices.length+1),()=>new Array(k+1).fill(-prices[0]));//天数和购买次数
    var DP_F = Array.from(new Array(prices.length+1),()=>new Array(k+1).fill(0));
    for(var i = 1;i<=prices.length;i++){
        for(var j = 1;j<=k;j++){ 
            DP_T[i][j] = Math.max(DP_T[i-1][j],DP_F[i-1][j-1] - prices[i-1] )
            DP_F[i][j] = Math.max(DP_F[i-1][j],DP_T[i-1][j] + prices[i-1] )
        }

    }
    return DP_F[prices.length][k]
};

所以就要在以前的不用DP数组的版本去改造,还有就是压缩K的值,因为一次交易由买入和卖出构成,至少需要两天。所以说有效的限制 k 应该不超过 n/2

        var maxProfit = function(k, prices) {
            if (k > prices.length / 2) {
                k = Math.floor(prices.length / 2); 
            
            }
        var obj = Array.from(new Array(k+1),() => ({
            'DP_F': 0,
            'DP_T': -prices[0]
        }))
        for(var i = 0;prices.length>i;i++){
            for(var j = 1;j<=k;j++){
                obj[j].DP_F = Math.max(obj[j].DP_F, obj[j].DP_T + prices[i] )
                obj[j].DP_T = Math.max(obj[j].DP_T, obj[j-1].DP_F- prices[i] )
            }
        }
        return  obj[k].DP_F
};

WeChat9372a55c1ced0d39143175d97bcf7aa1.png

  标签: 动态规划

非特殊说明,本博所有文章均为博主原创。

上一篇 正则匹配
下一篇 没有了

评论啦~