广州建设官方网站,wordpress 付费 破解,上海住房建设部官方网站,下载网上国网app文章目录 问题状态的定义与理解状态定义状态转移函数困惑思考 反思参考资料 问题
股票买卖问题是动态规划中常考的题型#xff0c;题目一般是给一个 p r i c e s prices prices的数组#xff0c;每个元素代表当天的股票价格#xff0c;再给你一个 k k k值#xff0c;代表允… 文章目录 问题状态的定义与理解状态定义状态转移函数困惑思考 反思参考资料 问题
股票买卖问题是动态规划中常考的题型题目一般是给一个 p r i c e s prices prices的数组每个元素代表当天的股票价格再给你一个 k k k值代表允许交易的最大次数最终让你求出能获得的最大利润。
状态的定义与理解
状态定义 d p [ i ] [ k ] [ s ] dp[i][k][s] dp[i][k][s] i i i第 i i i天 k k k交易的最大次数这里有很多歧义理解部分重点解释 s s s持有状态0代表不持有1代表持有。
举个例子 d p [ 3 ] [ 1 ] [ 0 ] dp[3][1][0] dp[3][1][0]代表在第三天我至今最多进行了1次交易现在没有持有的最大利润是多少。
状态转移函数
借用东哥的一个图理解下 d p [ i ] [ k ] [ 0 ] m a x ( d p [ i − 1 ] [ k ] [ 0 ] , d p [ i − 1 ] [ k ] [ 1 ] p r i c e s [ i ) dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k][1] prices[i) dp[i][k][0]max(dp[i−1][k][0],dp[i−1][k][1]prices[i)理解当天不持有的最大利润 m a x max max(前一天就不持有前一天持有但是今天卖出了) d p [ i ] [ k ] [ 1 ] m a x ( d p [ i − 1 ] [ k ] [ 1 ] , d p [ i − 1 ] [ k − 1 ] [ 0 ] − p r i c e s [ i ] ) dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) dp[i][k][1]max(dp[i−1][k][1],dp[i−1][k−1][0]−prices[i])理解当天不持有的最大利润 m a x max max(前一天就持有前一天不持有但是今天买入了)
这里有个细节是 k k k是在买入动作进行更新的。如果卖出的时候才更新会出现超出交易次数的限制。
困惑
这里我最开始看对 k k k的变化有个疑问
为什么计算 d p [ i ] [ k ] [ 1 ] dp[i][k][1] dp[i][k][1]的时候认为前一天不持有的状态是 d p [ i − 1 ] [ k − 1 ] [ 0 ] dp[i-1][k-1][0] dp[i−1][k−1][0]而不是 d p [ i − 1 ] [ k − 1 ] [ 0 ] dp[i-1][k-1][0] dp[i−1][k−1][0]
如果在 i i i天买入后的交易次数上限是 k k k i − 1 i-1 i−1天的交易次数上限不应该是 k 1 k1 k1吗怎么可能是 k − 1 k-1 k−1呢
不得不说这个地方东哥在书里的一句描述给了我很大的误解
思考
还是要回到 d p [ i ] [ k ] [ s ] dp[i][k][s] dp[i][k][s]的定义上来这个 k k k代表的到底是什么
理解1按照东哥上面红框这个描述我本来的理解是到第 i i i天我还「剩下的最大交易次数」❌理解2到第k天「已经进行的交易次数」❌理解3到第k天为止「最多已经进行的交易次数」✅ 其实在前文东哥举例子的时候是这么说的但是后面改了个说法我就晕了…笨笨子
为什么理解3就是通的呢还是回到我最初的那个困惑
为什么计算 d p [ i ] [ k ] [ 1 ] dp[i][k][1] dp[i][k][1]的时候认为前一天不持有的状态是 d p [ i − 1 ] [ k − 1 ] [ 0 ] dp[i-1][k-1][0] dp[i−1][k−1][0]而不是 d p [ i − 1 ] [ k 11 ] [ 0 ] dp[i-1][k11][0] dp[i−1][k11][0]
你想呀如果是理解1剩下的最大交易次数今天买入交易了一次变成了 k k k那昨天剩下的次数一定比今天多一次才行就应该是 d p [ i − 1 ] [ k 1 ] [ 0 ] dp[i-1][k1][0] dp[i−1][k1][0]。
如果是理解2状态转移函数和最后的返回值就要大改了显然不是一个合适的状态定义。
如果是理解3一切就合乎情理了本来题目说的也是最多允许交易 k k k次如果到第 i i i天最多已经进行的交易次数是 k k k且在第 i i i天我们进行了买入的操作那么第 i − 1 i-1 i−1天当然最多已经进行的交易次数是 k − 1 k-1 k−1了。
反思
股票买卖题型我至少刷了3次了竟然今天才产生这样的疑问说明之前理解的并不透彻更多是浮在表面的记忆层面一味追求提交通过。希望后面的刷题之路中多一点类似的深度思考真正弄懂弄透把刷题变成有趣的事情。
参考资料
《labuladong的算法小抄》
