动态规划是什么?我想一定是发生了某种不可抗的事情,我才会选择在帝都这么好的天气里面,写 动态规划的精髓在于「规划」,在于对问题的规划上面。当我们遇到一系列问题的时候,常常喜欢把复杂的问题分拆成小问题,动态规划也是对复杂问题的拆分,不过动态规划是更高级的拆分形式而已。高级的地方在于,复杂问题拆分成小问题的方式,同样适用于小问题分拆成更小的问题,也适用于更小的问题分拆成更更小的问题,直到不再是问题。 引用Wiki上的说法,是这样的。
我想读者朋友会忍不住吐槽,你TM说的是什么玩意 (ノ`Д′)ノ。我们从实际的例子出发,来看看是怎么回事。 跳台阶的问题小明最近在锻炼身体,坚持跳台阶上18层(真的敲厉害),小明一次可以跳一个台阶,也可以跳两个台阶,问小明有多少种方式可以上18层呢?这是一个非常经典的动态规划问题,我们假如只上一级台阶,那么有多少种方法呢?这里我们用 f(n) 来表示n级台阶的跳法。
聪明的你,一定想出来了, 具体的实现代码如下: 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毛钱需要的最少兑换硬币数目。 我们还是和前面一样进行分析
经过前面的分析,我们就可以得到如下的状态转移方程, 具体算法就能很轻松地写出来了,如果有疑问,请自行Google best time to buy and sell stock题目的意思是整个过程中只能买一只股票然后卖出,也可以不买股票。也就是我们要找到一对最低价和最高价,最低价在最高价前面,以最低价买入股票,以最低价卖出股票。 这是一道很经典的动态规划题目,原题链接点这里 这题就留给大家思考了,不做具体分析,只列出状态迁移方程,和对应代码
int maxProfit(vectorint> &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="">1], minprice); if(res < prices[i]="" -="" minprice)="" ="" ="" ="" ="" ="" res="prices[i]" -="" minprice;="" ="" }="" ="">if(res <>0){ return 0; } else { return res; }} 一点感想动态规划并没有我们认为的那么难懂,也不用把动态规划看做是老虎,它其实只是一种思路,一种思考的方式。我们在遇到各种难题的时候,也可以试试用动态规划的方式来解决我们当前的窘境,比如想想现在状态是什么样的,想要达到的状态是什么样的,我们如何变化才能达到理想状态,也许人生就是这么简单。 明天去参加 Qcon北京大会,在毕业后第一次去参加这种全球级别的峰会,确实感到有些兴奋。今年 Google AlphaGo 战胜人类棋手,棋类运动最后一片圣地也被贡献,至于是否这是天网一代的前身,人类命运几何,无从知晓,但真切地感受到,科技的车轮将无可阻挡地向前,这一切已经注定。
●本文编号180,以后想阅读这篇文章直接输入180即可。 ●输入m可以获取到文章目录。 更多推荐请看《15个技术类公众微信》 |
|