前端用动态规划玩股票
这篇文章和你去买股票没有半毛钱关系，既然你进来了，就来看看前端算法呗，嘿嘿嘿嘿！
前端没有需要刷算法？
为什么需要做算法题？大家其实都有发现在这一段2020年开始，各大公司对于前端的面试中，都不同程度的加入了算法题的测试，其中让大家最有感悟的就是字节跳动的前端面试，加入了大量的算法考验，其中不乏有很多在LeetCode上的中等以及困难题目，我也在知乎上发起了一个提问。浏览量上百万，也得到了很多的评论。
经过看了很多的评论，也明白了前端刷算法题的重要性，经过一段时间刷LeetCode，让我深有的体会的并不是这些算法在前端领域当中是否真的用到，而是算法能提高自身对于问题的理解能力，以及解决问题的能力，在刷了100多题之后，重新的自己的审视，发现自己对于同样问题的思考方式有一定的改变，所以暂且得出的结论是，刷算法对于前端开发来说，主要是提升自己的思考能力，以及对问题的分析能力。
本文概括
本文主要是讲述在LeetCode当中的股票类型题目使用动态规划的方式去解题的思路以及如何解题。
如果您已经做过，并深入理解，请阅读我的文章，看看我是否理解正确，如果你并没有做过该类题目，那么也可以阅读本文，先理解，然后关闭页面，打开LeetCode，尝试一下，挑战一下自己。
什么是动态规划（Dynamic Programming）？
在网上搜索动态规划可以得到很多很详细的答案，但是我个人觉得有很多回答都讲得太复杂了，对于一个前端开发来说，我们只需要知道以下几点：
- 动态规划具体是什么东西？
- 动态规划能解决什么类型的问题？
- 动态规划的优缺点是什么？
动态规划具体是什么东西？
动态规划在我理解里，动态规划并不是一个固定的算法，而是一个解决问题的思路。动态规划并不像一些我们平常经常了解到的什么快速排序，归并排序，冒泡排序等有一个固定的算法框架。动态规划更像是一种解决问题的思路。在之后的题目中会详细说到。
ps：在一开始接触到动态规划的时候，总是想去找一个固定的套路和规律去完成所有动态规划的题目，但是其实并没有固定的套路，只有相对来说比较有规律的解决思路。
动态规划能解决什么类型的问题？
按照我的理解就是动态规划主要可以解决在多个阶段中的最优方案，在理解动态规划之前，最好先了解一些什么叫贪心算法。其实贪心算法在我们日常去刷算法的时候，其实都会有无形中写出来过，贪心算法可以理解为在一个阶段中的最优解。而在刷了不少动态规划的题目中，其实可以得出一个结论，基本上可以用贪心算法解的题目，都可以用动态规划去解，但是动态规划解的题目，贪心算法不一定能解。在后面的题目中，会有更详细的描述，这里先做简单的了解。
什么叫做多个阶段中的最优解，例如在一个数组当中，找出最大的两组相加数字。 什么叫一个阶段中的最优解，例如在一个数组当中，找出最大的一组相加数组。
动态规划的优缺点是什么？
一个算法的好坏是通过时间复杂度以及空间复杂度去组成的。而在做动态规划的时候，一般都会以牺牲空间复杂度去换取时间复杂度的情况。当然在某些情况下，可以通过降维等方式，减少空间复杂度的牺牲成本。后续会有例子说明。
所以自己的总结就是动态规划的优点就是在某一些情况下，效率比贪心算法更高。但是在空间复杂度要求很高的情况下，动态规划不一定适合。
开始做题
本文主要从浅到深，一步一步做一些股票6部曲。
- 买卖股票的最佳时机和股票的最大利润 - 简单
- 买卖股票的最佳时机 II - 简单
- 最佳买卖股票时机含冷冻期 - 中等
- 买卖股票的最佳时机含手续费 - 中等
- 买卖股票的最佳时机 III - 困难
- 买卖股票的最佳时机 IV - 困难
买卖股票的组价时机/股票的最大利润
这一题是6部曲中一切的开始，也是比较简单的一题，相信大家看到题目后，不需要多久就能做出来，并且很容易就会用贪心算法进行实现。
分析：
题目中的数组是股票的每天金额，在股票里如何盈利，就是靠低买高卖来实现盈利的，而且题目中限制只能进行一次交易，并且不能在买入当天卖出，所以得出一个结论，我们需要在数组中找到一个最低价以及一个最高价，并且最高价的下标必须大于最低价的下标。
解题：
首先我们来看看暴力解法
var maxProfit = function ( prices ) {
if ( prices.length < 2 ) return 0;
const N = prices.length;
let max = 0;
for ( let i = 0; i < N; i++ ) {
for ( let n = i + 1; n < N; n++ ) {
max = Math.max( max, prices[n] - prices[i] );
}
}
return max;
}通过两层循环来找如果将i作为买入价，找出那天卖出的利润最佳。但是这里有一个问题，因为使用了双层循环，那么时间复杂度为n2，效率极低。
就算是暴力破解，其实也是用到贪心的思想，只是做法有点蠢。
优化一下代码，避免使用双层循环
var maxProfit = function ( prices ) {
if ( prices.length < 2 ) return 0;
const N = prices.length;
let max = 0;
let min = prices[0];
for ( let i = 1; i < N; i++ ) {
max = Math.max( max, prices[i] - min );
min = Math.min( min, prices[i] );
}
return max;
}通过在一次循环内，用当前记录的最小买入价 - 当前价格，得出是否最大利润，记录最小买入价。经过优化后，当前算法的时间复杂度是n，大大提升了效率，但是增加了一个min的变量，所以空间复杂度会有所提高。
动态规划：
要用动态规划，首先要看这一题目是否适合使用动态规划，从我的理解来看，本题是适合使用动态规划的，但是动态规划并非最好方式。首先这一题为什么是适合动态规划呢？从题目上，我们可以得知，每天的买入和卖出是会变化的，今天买入的价钱可能低于昨天买入的价钱，今天卖出的价钱可能高于昨天卖出的价钱。所以这里就涉及到了状态的转移。
状态在本题中，就是买入的价钱和卖出的价钱。而转移就是遇到更低的价格买入，遇到更高的价格卖出，在这一些列的话术中得出一个关键词：状态转移方程。
动态规划的思想，就是基于状态转移方程进行实现的，如何编写基于动态规划思想的代码，就必须先得出状态转移方程。
首先我们需要有2个状态：
- 不持股
- 持股
以下是状态转移方程：
- 不持股利润 = max(昨天不持股利润, 昨天持股利润 + 今天价格)
- 持股利润 = max(昨天持股利润, 今天价格)
可能一开始你看不懂这个计算公式，因为动态规划难的不是这个思想，而是如何设计这个状态转移方程。我用通俗的话去说或许你就明白了。
在每一个股市交易日里，我们只会有两种情况，买入今天价位的股票或者卖出你手上持有的股票，以题目为例，第一天的交易日里，我们的利润为0，因为并没有买入或卖出，但是我们如果选择今天买入股票，那么就是0 - 7 = -7。
在套入公式前，先说一下dp这个变量是什么。一般我们使用动态规划来解决问题，都会使用一个数组来表示每一个阶段的状态记录，一般我们都会命名为dp，按照题目为例:[7,6,4,3,1],共有5个交易日，那么dp的长度一般为5，分别记录每一天的状态。但是为了让大家更好理解，我们将dp设置成6。
按照上面的公式，让大家更好理解，我们就假设数组[7,6,4,3,1]分别代表的是周一~周六，但是我们设置dp数组为7，那么第一天的状态并不是周一，而是代表上一周的周日。
const dp = [
[], //周日
[], //周一
[], //周二
[], //周三
[], //周四
[], //周五
[] //周六
];
// 初始的周日状态，因为不是交易日，所以一切都是0
dp[0][0] = 0;
dp[0][1] = -Infinity; // 第一天设置为负无穷套入公式，那么第一天的状态转移方程如下：
- 不持股利润 = max(昨天不持股利润, 昨天持股利润 + 今天价格)
- 持股利润 = max(昨天持股利润, 今天价格)
dp[1][0] = Math.max( dp[0][0], dp[0][1] + prices[0] );
dp[1][1] = Math.max( dp[0][1], prices[0] );一般来说，第一天的状态我们都是可以预料的，所以一般我们会写成
const dp = new Array(N);
dp[0] = [];
dp[0][0] = 0;
dp[0][1] = -prices[0]; 第一天我们不可能持股，所以利润为0，但是第一天可以买入，但是我们周日是不可以交易的，所以周日的不持股利润为0，所以本质上是0 - 7，所以是-7，也可以简化写成-prices[0]。
根据状态转移方程，我们可以写出如下代码：
var maxProfit = function ( prices ) {
if ( prices.length < 2 ) return 0;
const N = prices.length;
const dp = new Array(N);
// 第一天
dp[0] = [];
dp[0][0] = 0;
dp[0][1] = -prices[0];
// 从第二天开始
for ( let i = 1; i < N; i++ ) {
// 设置第二天的状态
dp[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] );
}
// 以下是整个dp在一天的状态
// [ [ 0, -7 ], [ 0, -1 ], [ 4, -1 ], [ 4, -1 ], [ 5, -1 ], [ 5, -1 ] ]
return dp[N-1][0];
}
maxProfit( [7, 1, 5, 3, 6, 4] )最后最大的利润就是最后一天不持股状态下的利润。第一题必须搞清楚，因为后面的所有题目都是第一题的变形，所以多花点时间理解。
前面说到这一题使用动态规划并非最优解，那是因为动态规划是需要牺牲空间复杂度作为代价，记录每一个阶段的状态，每一个阶段的状态都是由上一个状态或者往上某个状态通过状态转移方程得出结果的。所以大家可以看到之前的暴力解法优化版和动态规划的空间复杂度就知道了，动态规划需要创建一个数组，所以空间复杂度是O(n),但是暴力解法的空间复杂度是O(1)。所以动态规划比暴力解法优化版差，但是这样就没有办法了吗？其实这里就引出一个动态规划的术语，降维或去维。
顾名思义，降维就是降低维度，去维就是去除维度，这里指的就是数组dp，例如一个二维数组的dp，降维就是将二维数组降为一维数组，去维就是将数组改为普通变量，从而将空间复杂度从O(n)变成O(1)。
在这一题中，其实是可以去维的，因为每一个状态的改变只关注上一个状态，所以我们可以如下优化代码：
var maxProfit = function ( prices ) {
if ( prices.length < 2 ) return 0;
const N = prices.length;
let dp_i_0 = 0;
let dp_i_1 = -prices[0];
for ( let i = 1; i < N; i++ ) {
dp_i_0 = Math.max( dp_i_0, dp_i_1 + prices[i] );
dp_i_1 = Math.max( dp_i_1, -prices[i] );
}
return dp_i_0;
}买卖股票的最佳时机2
分析：
从题目上可以看到和第一题基本一样，但是有一个条件不一样，就是不限制买卖次数，但是如果买入股票后，就必须卖出后才能再买进，而且买卖不能再同一天。所以要完成2次交易，最小需要4天时间。
解题：
和第一题一样，还是有2个状态
- 不持股
- 持股
第一题的状态转移方式：
- 不持股利润 = max(昨天不持股利润, 昨天持股利润 + 今天价格)
- 持股利润 = max(昨天持股利润, 今天价格)
因为这里只是规定了只有一次交易，所以持股（买入）时机只是看哪天买入比较低，但是在第二中，就没有那么简单了
回想第一题，在[7,1,5,3,6,4]中，最大的利润是在第二天，股票价格为1的时候买入，然后在第5天，股票价格为6的时候卖出，因为限制了只能买卖1次。
但是在第二题中，没限制买卖次数，那么大利润应该是第二天，股票价格为1的时候买入，然后第三天，股票价格为5的时候卖出，然后在第四天，股票价格为3的时候买入，在第五天，股票价格为6的时候卖出。
- 第一次买卖 = -1 + 5 = 4
- 第二次买卖 = -3 + 6 = 3
- 最终收益 = 4 + 3 = 7
基于第一题的状态转移方程，无法记录上一次买卖的收益，只能记录一次最大收益的买卖，那么我们要如何写第二题的状态转移方程呢？
首先不持股利润的方程是不需要改变的，因为无论怎么，不持股的利润都是用昨天的持股利润加上今天价格，和昨天不持股的利润做比较。
- 不持股利润 = max(昨天不持股利润, 昨天持股利润 + 今天价格)
所以关键就是持股利润的计算方式了，第一题的持股利润是和之前的不持股利润状态没有任何关系的。只是单纯的比较那天买入比较便宜。
我们用另外一个角度去想想，假设我现在没有进行过任何的买卖，我的不持股利润为0，那么我在第二天买入了价格为1的股票，那么我的钱包是不是应该是-1块，然后在第三天卖出该股票，那我是不是口袋里就有4块钱了，然后第四天我买入了价格为3的股票，那么我的钱包是不是剩下1块了，在第五天我以6块钱的价格卖出了股票，那我口袋是不是7块了。
所以我们可以想到，不持股利润是需要依赖持股利润 - 今日价格，所以持股利润需要与不持股的利润关联起来。所以持股的计算应该是昨天不持股的利润 - 今日价格。
- 不持股利润 = 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;
const dp = new Array( N );
dp[0] = [];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for ( let i = 1; i < N; i++ ) {
dp[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[N - 1][0];
}这里我们也可以用到去维
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_i_0 = 0; // 卖出后的利润
let dp_i_1 = -prices[0]; // 买入后的利润
for ( let i = 1; i < N; i++ ) {
const temp = dp_i_0; // 保留转换前的值提供给dp_i_1做计算
// 是否卖出是根据买入后的利润+今天价钱，是否比不卖出的高来确定是否卖出
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;
};有兴趣的可以试试用贪心如何来解题！
总结
我们通过这么一个经典的动态规划题目，去了解基本的动态规划的使用方式，以及一些基本的思想，在后面会持续更新后面每一题的解题方式以及不一样的地方，但是凡事必须从浅入深，要好好了解本篇文章讲到的知识点，在后面的题目中都会用到。
本篇先说两题最简单的题目，通过题目了解动态规划并非一个固定格式的算法，而是一个解决问题的思想，就像上面题目一样，我们需要把什么时候买入以及什么时候卖出的条件列举，写出状态转移方程，其实就已经完成90%了，剩下只是将状态转移方程变为代码即可。