昨天同事说动态规划很难，我说不会啊，理解了就很简单，我同事表示不屑，以为我在炫技。于是乎我问了一个工作六年的前同事，他居然也觉得高大上，并且表示接触过会动态规划的朋友，觉得很牛逼。
我了个天，表示震惊了，简直吓的我瑟瑟发抖发抖好么。既然如此，那我一定要让大家理解，让大家也牛逼牛逼。
以题举例
以中国leetcode（力扣）的121道题《买卖股票的最佳时机》举例，题目如下：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
首先说明一点，在这道题动态规划并不算是高效的算法，这道题即使是暴力法也能比动态规划法要快一些，但本文是为了讲动态规划才讲这道题的，而非为了这道题讲动态规划的。纯粹是这道题讲动态规划更简单。
不了解动态规划的朋友可能不知道，动态规划几乎都是存在套路的，步骤如下：
- 将问题拆解成单一问题制表
- 根据表中结果进行求解
第一步：将问题拆解成单一问题制表
这是动态规划的重中之重，拆的好坏基本决定你动态规划写的好坏，动态规划更是一种思想。
这道题就很简单了，我们可以把这个问题，先拆成单一问题，即如果我在这天买入，在哪天卖出最高？
我们按题目中的示例 1举例，价格数组为[7,1,5,3,6,4]。
比如我在第一天买入，在哪天卖出最高呢？我们可以得到这样一张表(不能交易标记X)：
| 买入时间 | 买入价格 | 单天价格 | 7 | 1 | 5 | 3 | 6 | 4 |
|---|---|---|---|---|---|---|---|---|
| – | – | 卖出时间 | 第一天 | 第二天 | 第三天 | 第四天 | 第五天 | 第六天 |
| 第一天 | 7 | 获利程度 | X | -6 | -2 | -4 | -1 | -3 |
填表原因如下：
- 即因为你是第一天买入的，所以第一天不能交易，所以填X
- 我们第一天买入的，买入价格为7，第二天值1，所以我们卖出则赚了-6.
- 我们第一天买入的，买入价格为7，第三天值5，所以我们卖出则赚了-2.
- 我们第一天买入的，买入价格为7，第四天值3，所以我们卖出则赚了-4.
- 我们第一天买入的，买入价格为7，第五天值6，所以我们卖出则赚了-1.
- 我们第一天买入的，买入价格为7，第六天值4，所以我们卖出则赚了-3.
有人说这个不是暴力解法么？额，这道题的动态规划的制表过程确实有点像。
那么根据以上规则，如果我们是第二天买入的话，这个表格是不是就是这样的。
| 买入时间 | 买入价格 | 单天价格 | 7 | 1 | 5 | 3 | 6 | 4 |
|---|---|---|---|---|---|---|---|---|
| – | – | 卖出时间 | 第一天 | 第二天 | 第三天 | 第四天 | 第五天 | 第六天 |
| 第二天 | 1 | 获利程度 | X | X | 4 | 2 | 5 | 3 |
那么我合并这两张表是不是就是这样的：
| 买入时间 | 买入价格 | 单天价格 | 7 | 1 | 5 | 3 | 6 | 4 |
|---|---|---|---|---|---|---|---|---|
| – | – | 卖出时间 | 第一天 | 第二天 | 第三天 | 第四天 | 第五天 | 第六天 |
| 第一天 | 7 | 获利程度 | X | -6 | -2 | -4 | -1 | -3 |
| 第二天 | 1 | 获利程度 | X | X | 4 | 2 | 5 | 3 |
那么我们把这张表弄完整，即把第三天到第五天的买入，那是不是就是这样的。
| 买入时间 | 买入价格 | 单天价格 | 7 | 1 | 5 | 3 | 6 | 4 |
|---|---|---|---|---|---|---|---|---|
| – | – | 卖出时间 | 第一天 | 第二天 | 第三天 | 第四天 | 第五天 | 第六天 |
| 第一天 | 7 | 获利程度 | X | -6 | -2 | -4 | -1 | -3 |
| 第二天 | 1 | 获利程度 | X | X | 4 | 2 | 5 | 3 |
| 第三天 | 5 | 获利程度 | X | X | X | -2 | 1 | -1 |
| 第四天 | 3 | 获利程度 | X | X | X | X | 3 | 1 |
| 第五天 | 6 | 获利程度 | X | X | X | X | X | -2 |
| 第六天 | 4 | 获利程度 | X | X | X | X | X | X |
因为第六天买了的话，已经是最后一天了，所以没办法卖了，所以全是X。
第二步：根据表中结果进行求解
上一步，已经把如果是某天买的，每天的获利情况列了一遍，就是拆解成了单一问题。
那么看最大利润，很容易就能看出来了，就看那个数字最大就好了。
| 买入时间 | 买入价格 | 单天价格 | 7 | 1 | 5 | 3 | 6 | 4 |
|---|---|---|---|---|---|---|---|---|
| – | – | 卖出时间 | 第一天 | 第二天 | 第三天 | 第四天 | 第五天 | 第六天 |
| 第一天 | 7 | 获利程度 | X | -6 | -2 | -4 | -1 | -3 |
| 第二天 | 1 | 获利程度 | X | X | 4 | 2 | 5⃣️ | 3 |
| 第三天 | 5 | 获利程度 | X | X | X | -2 | 1 | -1 |
| 第四天 | 3 | 获利程度 | X | X | X | X | 3 | 1 |
| 第五天 | 6 | 获利程度 | X | X | X | X | X | -2 |
| 第六天 | 4 | 获利程度 | X | X | X | X | X | X |
没错emoji的5的就是，那么我们只要简单的遍历一下这个表是不是就能把结果取出来了？嗯，对的
最后
但一般来说动态规划的题目不是这么简单的，通常在制表的时候会涉及一个叠加问题，在根据表计算结果一般也不是简单的遍历就能完成的，但理解动态规划思想应该是没什么问题了。
个人认为动态规划虽然性能不强，但是能把问题变得很直观，让人更简单的解决问题。同时算法的杂合度不高，很方便使用分布式为问题的每个单一问题进行求解。
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let max = 0;
let min = prices[0];
for (let i = 1; i < prices.length; i++) {
if (prices[i] < min) {
min = prices[i];
} else {
max = Math.max(prices[i] - min, max)
}
}
return max;
};
股票价位没有等于0的情况
你是不是想把价位最低的剔掉
while (prices.length>0) {
if (prices[prices.length-1] === Math.min.apply(this,prices)) {
prices.pop();
} else {
break;
}
}
@fuxingZhang 这道题解法其实很多，我主要是讲解动态规划，并不是讲解这道题的解法。 在这道题里面，因为动态规划本来性能就不好，所以只能使用优化首尾的方式（踢出首部最高价，踢出尾部最低价）来勉强过关。 主要是很多人觉得动态规划是特别高大上的东西，而且网上题解都是相对经典的题目，而这些题目很多没花时间看的人，就很容易迷糊。 我写这个稍微扫两眼，基本能知道动态规划是如何解题的。
动态规划必须用二维数组吗
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
// 优化头
while (prices.length > 0) {
let maxPrice = Math.max.apply(null, prices);
if (maxPrice <= prices[0]) {
prices.shift();
} else {
break;
}
}
// 优化尾
while (prices.length > 0) {
if (prices[prices.length - 1] === Math.min.apply(null, prices)) {
prices.pop();
} else {
break;
}
}
// 开始动态规划填表
const dpTable = [];
for (let i = 0; i < prices.length - 1; i++) {
for (let j = i + 1; j < prices.length; j++) {
dpTable.push(prices[j] - prices[i]);
}
}
return Math.max.apply(null, dpTable);
};
