动态规划难?读完这篇还不理解那就不要请我吃鸡了
发布于 3 年前 作者 zy445566 2952 次浏览 来自 分享

昨天同事说动态规划很难,我说不会啊,理解了就很简单,我同事表示不屑,以为我在炫技。于是乎我问了一个工作六年的前同事,他居然也觉得高大上,并且表示接触过会动态规划的朋友,觉得很牛逼。

我了个天,表示震惊了,简直吓的我瑟瑟发抖发抖好么。既然如此,那我一定要让大家理解,让大家也牛逼牛逼。

以题举例

以中国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. 将问题拆解成单一问题制表
  2. 根据表中结果进行求解

第一步:将问题拆解成单一问题制表

这是动态规划的重中之重,拆的好坏基本决定你动态规划写的好坏,动态规划更是一种思想。

这道题就很简单了,我们可以把这个问题,先拆成单一问题,即如果我在这天买入,在哪天卖出最高? 我们按题目中的示例 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的就是,那么我们只要简单的遍历一下这个表是不是就能把结果取出来了?嗯,对的

最后

但一般来说动态规划的题目不是这么简单的,通常在制表的时候会涉及一个叠加问题,在根据表计算结果一般也不是简单的遍历就能完成的,但理解动态规划思想应该是没什么问题了。

个人认为动态规划虽然性能不强,但是能把问题变得很直观,让人更简单的解决问题。同时算法的杂合度不高,很方便使用分布式为问题的每个单一问题进行求解。

本题代码:best-time-to-buy-and-sell-stock.js

8 回复

厉害,厉害 👍,通俗易懂

/**
 * @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的情况 image.png

你是不是想把价位最低的剔掉

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);
};

@fuxingZhang 不一定,主要看问题的复杂度

@zy445566 学习了,第一次听说动态规划

回到顶部