也来谈谈动态规划

我想一定是发生了某种不可抗的事情,我才会选择在帝都这么好的天气里面,写动态规划这么操蛋的事情。可这是我的小秘密,我并不打算告诉你。

动态规划的精髓在于「规划」,在于对问题的规划上面。当我们遇到一系列问题的时候,常常喜欢把复杂的问题分拆成小问题,动态规划也是对复杂问题的拆分,不过动态规划是更高级的拆分形式而已。高级的地方在于,复杂问题拆分成小问题的方式,同样适用于小问题分拆成更小的问题,也适用于更小的问题分拆成更更小的问题,直到不再是问题。

引用Wiki上的说法,是这样的。

动态规划是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。

我想读者朋友会忍不住吐槽,你TM说的是什么玩意 (ノ`Д´)ノ。我们从实际的例子出发,来看看是怎么回事。

跳台阶的问题

小明最近在锻炼身体,坚持跳台阶上18层(真的敲厉害),小明一次可以跳一个台阶,也可以跳两个台阶,问小明有多少种方式可以上18层呢?这是一个非常经典的动态规划问题,我们假如只上一级台阶,那么有多少种方法呢?这里我们用 f(n) 来表示n级台阶的跳法。

感谢晓笶同学细心的阅读,这里修正了错误。

  • 对于平台而言,就是原地,也就是说 f(0) = 1;
  • 对于一级台阶而言,很简单,就是一步跳上去,所以 f(1) = 1;
  • 对于二级台阶而言,我们来分拆下这个问题,只看最后一下是怎么上得二级台阶,根据题意,要么最后一次跳2步,要么最后一次跳1步;小明如果选择一次跳2步的话,那么就有f(2-2); 这是一种方式,那么如果小明选择一次跳1步的话,f(2-1) ; 换而言之,就是f(2) = f(2-2) + f (2-1);
  • 对于三级台阶而言,继续分拆这个问题,最后一步跳2级的话,有这么多种跳法 f (3 - 2) = f(1),如果最后一次跳1级的话,有f(3-1)=f(2) 种跳法;
  • … …
  • 现在我们可以对问题进行归纳了,上n级台阶的做法 等于 上n-2级台阶的做法 加上 上n-1级台阶的做法

聪明的你,一定想出来了,f(n) = f(n-1) + f(n-2), 在这里,我们将 f(n) 称之为状态,f(n) = f(n) + f(n-1) 成为状态转移方程。

具体的实现代码如下:

long long fibonacci(unsigned int n){
    int result[3] = {0, 1, 2};
    if (n <= 2)
        return result[n];

    return fibonacci(n - 1) + fibonacci(n - 2);
}

动态规划是也就是寻找一种对问题的观察角度,通过分析构建状态,以及定义状态是如何进行转换的,就能从起始状态出发达到最终状态,让问题能够以递推(或者说分治)的方式去解决。

最小硬币数量

对动态规划初步认识后,再来看看下面的一个例子,加深一下理解。

小明的奶奶,纵横菜市场多年,是位非常睿智慈祥的退休老师。有一天,小明不知道从哪弄到了很多1,2,5毛的硬币,奶奶舍不得这么多硬币,于是就想办法去菜市场花掉这些硬币,但出于面子,又不能每次都用1毛的硬币去买菜,问题来了,有什么方法可以快速帮奶奶用最少的硬币数量来付菜钱?

这也是一道动态规划的题目,我们先来看看状态的定义。这里的状态比较明显就是,f(n)为 n毛钱需要的最少兑换硬币数目。

我们还是和前面一样进行分析

  • f(0) = 0; 因为没有钱,也就没有硬币可兑换
  • f(1) = f(1-0) + 1;我们来分析下,1毛钱只能用1毛硬币来兑换,所以我们拿起了1毛硬币,剩下的钱就是(1-0),所以需要的硬币个数,就是1 + f(1-0)
  • f(2) = min{ f(2-1) + 1, f(2-2) + 1}; 继续分析,2毛钱可是大钱,我们有2种方法,来进行兑换,一个用1毛的硬币,所以个数就是 1 + f(2-1), 或者我们用一个2毛的硬币,个数就是 1 + f(2-2), 题目中说的是最小个数,因而我们取2者中的最小值;

经过前面的分析,我们就可以得到如下的状态转移方程,f(n)=min{ f(n-price(i))+1 },其中price(i)表示第i个硬币的面值。

具体算法就能很轻松地写出来了,如果有疑问,请自行Google

best time to buy and sell stock

题目的意思是整个过程中只能买一只股票然后卖出,也可以不买股票。也就是我们要找到一对最低价和最高价,最低价在最高价前面,以最低价买入股票,以最低价卖出股票。

这是一道很经典的动态规划题目,原题链接点这里

这题就留给大家思考了,不做具体分析,只列出状态迁移方程,和对应代码

f(n+1) = max{f(n), prices(n+1) - minPrices(n)}, 其中 prices[i]表明第i天的股票价格,minPrices(i)是区间[0,1,2…,i]内的最低价格。用白话文来说,今天截止时最大的收入是 前一天收入今天价格与前面最低价之间的差额 的最大值。

int maxProfit(vector<int> &prices) {
    // IMPORTANT: Please reset any member data you declared, as
    // the same Solution instance will be reused for each test case.
	int len = prices.size();
	if(len <= 1) {
		return 0;
	}
	int res = prices[1] - prices[0], minprice = prices[0];
	for(int i = 2; i < len; i++){
		minprice = min(prices[i-1], minprice);
		if(res < prices[i] - minprice)
			res = prices[i] - minprice;
	}
	if(res < 0){
		return 0;
	} else {
		return res;
	}
}

一点感想

动态规划并没有我们认为的那么难懂,也不用把动态规划看做是老虎,它其实只是一种思路,一种思考的方式。我们在遇到各种难题的时候,也可以试试用动态规划的方式来解决我们当前的窘境,比如想想现在状态是什么样的,想要达到的状态是什么样的,我们如何变化才能达到理想状态,也许人生就是这么简单。

明天去参加 Qcon北京大会,在毕业后第一次去参加这种全球级别的峰会,确实感到有些兴奋。今年 Google AlphaGo 战胜人类棋手,棋类运动最后一片圣地也被贡献,至于是否这是天网一代的前身,人类命运几何,无从知晓,但真切地感受到,科技的车轮将无可阻挡地向前,这一切已经注定。明天 去现场参观下 Qcon,感受下现在的科技脉搏。

Published: April 22 2016