镇江房产网:从“股票问题”谈动态计划问题的解决思绪

admin 5个月前 (05-20) 科技 50 1

总体思绪

    有过在Leetcode上演习履历的同砚们对股票问题一定不会感应生疏,动态计划问题的焦点在于寻找状态转移方程,对于通例的动态计划问题,如零钱问题、背包问题,我们可能会以为状态转移方程找起来并不费劲,但对于股票问题,可能许多同砚都以为状态转移方程难找。在我对股票问题举行了反复研究之后,我发现实在之所以股票系列剖析存在这种难题,并不是“转移方程难找”,而是其具有多个维度的“状态”,其状态的庞大性导致我们在没有处置好状态的情形下便谈不上解决“转移方程”的问题。

状态的确定与处置?

首先我们要思量的是状态有哪些,详细到本题,共有三个维度的状态:

  1. 天数
  2. 允许生意的最大次数
  3. 用户账户当前状态(持有或者未持有股票)

其次是若何处置状态,实在人人可以细细回忆,对于动态计划问题我们处置状态,虽然你可能没有注重,实在使用的是“穷举”头脑,比如说背包问题中的物品数目和背包容量。至于怎么枚举,看下面的伪代码你一定就明了啦!

for 状态1 in 状态1的所有取值:
    for 状态2 in 状态2的所有取值:
        for ...
            dp[状态1][状态2][...] = 择优(选择1,选择2...)

该伪代码参考自Leetcode,个人认为这个状态枚举思绪的伪代码写的非常好,然则作者对于股票问题状态划分有些庞大。
那详细到本题,我们的状态框架如下

dp[i][k][0 or 1] //前面说了三个维度,自然dp数组也是三维的
for(int i = 0;i < n;i++)
    for(int j = 0;j < k;j++)
        dp[i][j][0] 取优
        dp[i][j][1] 取优//账户状态这个维度只有两种可能,就直接盘算就好啦。

那我们接下里将通过对股票问题的详细实例解说的方式来先容详细解法,现在剩下的实在就是个状态转移方程的事情啦。

各个击破

k = 1的情形

121. 生意股票的最佳时机
k = 1是思绪很清晰,实在只需要直接一趟遍历,而且记录下当前元素之前的最小元素并行使其盘算当前天卖出最大收益即可。这个实在感受不算典型动态计划。


class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0)
            return 0;
        int min = prices[0],max = 0;
        for(int i = 1;i < prices.length;i++){
            max = Math.max(max,prices[i] - min);
            min = Math.min(min,prices[i]);
            
        }
        return max;
    }
}

k值不受限

122. 生意股票的最佳时机 II

枚举框架

根据我们最最先的状态枚举框架,k不受限即早年向后遍历(领会完全背包问题的同砚一定熟悉),而且不设置k维度即可(只有天数、账户状态两个维度)。

状态转移方程

当前天未持有,则有两种情形:
1、昨天就未持有,今天也不买,则为dp[i - 1][0]
2、昨天持有,今天卖出,则为dp[i - 1][1] + prices[i])
综上,二者取优
dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] + prices[i]);
同样,当前天持有也是两种情形:
1、昨天持有,则为dp[i - 1][1]
2、昨天未持有,今天买入dp[i - 1][0] - prices[i]
综上,二者取优
dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];//0为未持有,1为持有
        dp[0][0] = 0;
        dp[0][1] = 0 - prices[0];
        for(int 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],dp[i - 1][0] - prices[i]);
        }
        return dp[prices.length - 1][0];
    }
}

k值不受限且包罗冷冻期

309. 最佳生意股票时机含冷冻期

枚举框架

根据我们最最先的状态枚举框架,k不受限即早年向后遍历(领会完全背包问题的同砚一定熟悉),而且不设置k维度即可(只有天数、账户状态两个维度)。

状态转移方程

当前天未持有,则有两种情形:
1、昨天就未持有,今天也不买,则为dp[i - 1][0]
2、昨天持有,今天卖出,则为dp[i - 1][1] + prices[i - 1]),注重,price从0最先索引
综上,二者取优
dp[i][0] = Math.max(dp[i - 1][1] + prices[i - 1],dp[i - 1][0]);
同样,当前天持有也是两种情形,但由于存在冷冻期,买出的话需要从i-2转移过来:
1、昨天持有,则为dp[i - 1][1]
2、昨天未持有,今天买入dp[i - 2][0] - prices[i - 1]
综上,二者取优
dp[i][1] = Math.max(dp[i - 1][1],i - 2 >= 0 ? dp[i - 2][0] - prices[i - 1]: 0 - prices[i - 1])

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length + 1][2];
        dp[0][1] = Integer.MIN_VALUE;
        for(int i = 1;i <= prices.length;i++){
            dp[i][0] = Math.max(dp[i - 1][1] + prices[i - 1],dp[i - 1][0]);
            dp[i][1] = Math.max(dp[i - 1][1],i - 2 >= 0 ? dp[i - 2][0] - prices[i - 1]: 0 - prices[i - 1]);
        }
        return dp[prices.length][0];
    }
}

k值不受限且包罗手续费

状态转移方程与k值不受限完全相同,只是卖出时要减手续费即可

枚举框架

根据我们最最先的状态枚举框架,k不受限即早年向后遍历(领会完全背包问题的同砚一定熟悉),而且不设置k维度即可(只有天数、账户状态两个维度)。

状态转移方程

当前天未持有,则有两种情形:
1、昨天就未持有,今天也不买,则为dp[i - 1][0]
2、昨天持有,今天卖出,则为dp[i - 1][1] + prices[i] - fee)
综上,二者取优
dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] + prices[i] - fee);
同样,当前天持有也是两种情形:
1、昨天持有,则为dp[i - 1][1]
2、昨天未持有,今天买入dp[i - 1][0] - prices[i]
综上,二者取优
dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int[][] dp = new int[prices.length][2];//0为未持有,1为持有
        dp[0][0] = 0;
        dp[0][1] = 0 - prices[0];
        for(int i = 1;i < prices.length;i++){
            dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] + prices[i] - fee);
            dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);
        }
        return dp[prices.length - 1][0];
    }
}

k为随便整数

188. 生意股票的最佳时机 IV

枚举框架

枚举框架与本文最最先剖析的思绪完全相同,只需要对天、最大生意次数、账户状态这三个维度举行枚举即可。

状态转移方程

当前天未持有,则有两种情形:
1、昨天就未持有,今天也不买,且显然这种情形不会增添生意次数,则为dp[i - 1][j][0]
2、昨天持有,今天卖出,卖出操作并不会增添生意次数,仍然是本生意次数维度举行转移,为dp[i - 1][j][1] + prices[i]
综上,二者取优
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
同样,当前天持有也是两种情形:
1、昨天持有,则为dp[i - 1][j][1]
2、昨天未持有,今天买入,注重买入会引起生意次数转变,所以为dp[i - 1][j - 1][0] - prices[i]
综上,二者取优
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);

class Solution {
    public int maxProfit(int k, int[] prices) {
        if(prices == null || prices.length < 2)
            return 0;
        int[][][] dp = new int[prices.length][k + 1][2];//0是未持有,1是持有
        for(int i = 0;i <= k;i++){//第一天base case
            dp[0][i][1] = 0 - prices[0];
        }
        for(int i = 1;i < prices.length;i++){
            for(int j = 1;j <= k;j++){
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
            }
        }
        return dp[prices.length - 1][k][0];
    }
}

总结

看到这里,实在我们就会明了,动态计划实在要确定的三部门就是:

  1. dp语义
  2. 状态枚举框架
  3. 转移方程

确定了这三样,一切便都迎刃而解了。

,

Sunbet

菲律宾长滩岛旅游攻略最专业权威的媒体人搜集社会热点资讯,推送内容精准可靠,针对用户个性化需求,整合各界热点专题,以新媒体传播的方式挖掘最新最热门资讯,为您提供您感兴趣的新闻与生活内容, 涵盖了时政、财经、社会、教育、情感等全方位多角度的新闻报道分析,同时开拓您的眼界和思路,让您足不出户就能一揽天下。

皇冠体育声明:该文看法仅代表作者自己,与本平台无关。转载请注明:镇江房产网:从“股票问题”谈动态计划问题的解决思绪

网友评论

  • (*)

最新评论

  • 申傅新网址 2020-05-20 00:11:18 回复

    sunbet:www.ysycy.com与伊顺源清真餐饮达成战略合作,在伊顺及亚太地区建立直营平台。为Sunbet会员提供线上多种娱乐游戏,将用完善的技术、贴心的服务、雄厚的资金赢取每位Sunbet代理、会员的口碑。送你一枝玫瑰花。

    1

文章归档

站点信息

  • 文章总数:625
  • 页面总数:0
  • 分类总数:8
  • 标签总数:1148
  • 评论总数:268
  • 浏览总数:8678