前端用动态规划玩股票 - 最终章
source link: https://zhuanlan.zhihu.com/p/159319753
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
前端用动态规划玩股票 - 最终章
这篇文章和你去买股票没有半毛钱关系，既然你进来了，就来看看前端算法呗，嘿嘿嘿嘿！
前端没有需要刷算法？
为什么需要做算法题？大家其实都有发现在这一段2020年开始，各大公司对于前端的面试中，都不同程度的加入了算法题的测试，其中让大家最有感悟的就是字节跳动的前端面试，加入了大量的算法考验，其中不乏有很多在LeetCode上的中等以及困难题目，我也在知乎上发起了一个提问。浏览量上百万，也得到了很多的评论。
经过看了很多的评论，也明白了前端刷算法题的重要性，经过一段时间刷LeetCode，让我深有的体会的并不是这些算法在前端领域当中是否真的用到，而是算法能提高自身对于问题的理解能力，以及解决问题的能力，在刷了100多题之后，重新的自己的审视，发现自己对于同样问题的思考方式有一定的改变，所以暂且得出的结论是，刷算法对于前端开发来说，主要是提升自己的思考能力，以及对问题的分析能力。
本文主要是讲述在LeetCode当中的股票类型题目使用动态规划的方式去解题的思路以及如何解题。
如果您已经做过，并深入理解，请阅读我的文章，看看我是否理解正确，如果你并没有做过该类题目，那么也可以阅读本文，先理解，然后关闭页面，打开LeetCode，尝试一下，挑战一下自己。
本篇文章是前端用动态规划玩股票的最终章，这次我们来挑战一下LeetCode中股票题目中的困难两题：
如果你并没有看过之前的两篇文章，建议先仔细阅读再看最终章。
买卖股票的组价时机III
这一题中，是基于第二题《买卖股票的最佳时机2》的基础上，加上了购买次数的限制。本题中限制了最多只能购买2次的限制，但是并非必须购买2次。所以我们可以想到第二次购买必须是第一次非持有股票的利润 - 今日股价来决定是否买入的。
因为这里涉及到了限制2次购买，所以一共有4个状态
- 第一次 非持股
- 第一次 持股
- 第二次 非持股
- 第二次 持股
在这里我们可以回顾一下第一题《买卖股票的最佳时机》时候我们的状态转移方程，因为只限制1次购买，与这里第一次持股的条件一样，并不存在累加利润的情况，只需要找到比当前持股成本更低和非持股的利润更高的状态即可，所以这里第一次买卖的状态转移方程就得出了。
- 第一次 不持股利润 = max(第一次昨天不持股利润, 第一次昨天持股利润 + 今天价格)
- 第一次 持股利润 = max(第一次昨天持股利润, 今天价格)
那么第二次买卖的状态转移方程怎么写呢？
首先我们要清楚，第二次购买肯定是在第一次购买后，所以第二次的持股条件应该是基于第一次非持股时的利润进行计算，所以得出第二次购买的状态转移方程。
- 第二次 不持股利润 = max(第二次昨天不持股利润, 第二次昨天持股利润 + 今天价格)
- 第二次 持股利润 = max(第二次昨天持股利润, 第一次不持股利润 - 今天价格)
代码实现：
var maxProfit = function ( prices ) {
if ( prices.length <= 1 ) return 0;
if ( prices.length == 2 ) return Math.max( 0, prices[1] - prices[0] );
const N = prices.length;
// 第一次交易
let dp_0_0 = 0; // 卖出后的利润
let dp_0_1 = -prices[0]; // 买入后的利润
// 第二次交易
let dp_1_0 = 0; // 卖出后的利润
let dp_1_1 = -prices[0]; // 买入后的利润
for ( let i = 1; i < N; i++ ) {
// 第二次卖出 根据当前买入后的利润 + 今日金额
dp_1_0 = Math.max( dp_1_0, dp_1_1 + prices[i] );
// 第二次买入，当前买入后的利润 是否大于 第一次买入后的利润 - 今日金额
dp_1_1 = Math.max( dp_1_1, dp_0_0 - prices[i] );
// 第一次买出，卖出条件是当前买入后利润+今日金额 是否大于 当前卖出的总利润
dp_0_0 = Math.max( dp_0_0, dp_0_1 + prices[i] );
// 都一次买入，判断是否有更低的买入价
dp_0_1 = Math.max( dp_0_1, -prices[i] );
}
return dp_1_0;
}
买卖股票的组价时机IV
最后一题和上一题其实是一样，只是将限制购买2次变为n次。
所以状态转移方程是和上一题一样的，但是有一些不一样，就是需要区分是否为第一次买卖。
- 第一次 不持股利润 = max(第一次昨天不持股利润, 第一次昨天持股利润 + 今天价格)
- 第一次 持股利润 = max(第一次昨天持股利润, 今天价格)
- 第n次 不持股利润 = max(第n次昨天不持股利润, 第n次昨天持股利润 + 今天价格)
- 第n次 持股利润 = max(第n次昨天持股利润, 第n-1次不持股利润 - 今天价格)
在编写代码的时候就需要留意了，在这一题中，我们就不能去维了，因为购买的次数的n次，所以我们就需要dp数组来记录每一次的买卖记录了。
代码实现：
var maxProfit = function(k, prices) {
const N = prices.length;
if (N <= 1 || k < 1) return 0;
// 当限定的购买天数大于可购买天数的一半，可以视为没有任何限制
if ( k > N / 2 ) {
let dp_i_0 = 0;
let dp_i_1 = -prices[0];
for ( let i = 1; i < N; i++ ) {
const temp = dp_i_0;
dp_i_0 = Math.max( dp_i_0, dp_i_1 + prices[i] );
dp_i_1 = Math.max( dp_i_1, temp - prices[i] );
}
return dp_i_0;
}
// 不确定传入的限制次数是多少，所以不能进行降维处理
// 构建dp;
const dp = [];
for ( let i = 0; i < N; i++ ) {
dp[i] = [];
for ( let n = 0; n < k; n++ ) {
if ( i == 0 ) {
dp[i][n] = [0, -prices[0]]
} else {
dp[i][n] = [0,0];
}
}
}
// 循环天数
for ( let i = 1; i < N; i++ ) {
// 循环限制购买次数，倒序
for ( let n = k - 1; n >= 0; n-- ) {
// 需要区分第一次买卖还是非第一次买卖
dp[i][n][0] = Math.max( dp[i-1][n][0], dp[i-1][n][1] + prices[i] );
dp[i][n][1] = Math.max( dp[i-1][n][1], n == 0 ? -prices[i] : dp[i-1][n-1][0] - prices[i] );
}
}
return dp[N-1][k-1][0];
};
以上就是所有股票的题目解法，其实只要知道第一第二题的状态转移方程，其实就比较好得出后面的其他买卖条件下的状态转移方程了。
经过这几题股票题目，可以大概了解到动态规划的大概是使用方式，动态规划在很多大厂都有不少的面试题，主要是因为动态规划考验的并非具体的算法如何编写，而是背后的对问题的分析能力，以及如何将问题分解成小问题最终得出状态转移方程。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK