动态规划:从新手到专家 |
您所在的位置:网站首页 › 从奶爸开始到专家 › 动态规划:从新手到专家 |
(如果想学习动态规划(DP),这将是一篇很好的文章。本文来自:Hawstein--http://www.hawstein.com/posts/dp-novice-to-advanced.html)
前言
本文翻译自TopCoder上的一篇文章:Dynamic Programming: From novice to advanced,并非严格逐字逐句翻译,其中加入了自己的一些理解。水平有限,还望指摘。 前言_我们遇到的问题中,有很大一部分可以用动态规划(简称DP)来解。解决这类问题可以很大地提升你的能力与技巧,我会试着帮助你理解如何使用DP来解题。这篇文章是基于实例展开来讲的,因为干巴巴的理论实在不好理解。 注意:如果你对于其中某一节已经了解并且不想阅读它,没关系,直接跳过它即可。 简介(入门)什么是动态规划,我们要如何描述它? 动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度,因此它比回溯法、暴力法等要快许多。 现在让我们通过一个例子来了解一下DP的基本原理。 首先,我们要找到某个状态的最优解,然后在它的帮助下,找到下一个状态的最优解。 “状态”代表什么及如何找到它? “状态”用来描述该问题的子问题的解。原文中有两段作者阐述得不太清楚,跳过直接上例子。 如果我们有面值为1元、3元和5元的硬币若干枚,如何用最少的硬币凑够11元?(表面上这道题可以用贪心算法,但贪心算法无法保证可以求出解,比如1元换成2元的时候) 首先我们思考一个问题,如何用最少的硬币凑够i元(i=0,vj表示第j个硬币的面值; 有了状态和状态转移方程,这个问题基本上也就解决了。当然了,Talk is cheap,show me the code! 伪代码如下: 下图是当i从0到11时的解: 从上图可以得出,要凑够11元至少需要3枚硬币。 此外,通过追踪我们是如何从前一个状态值得到当前状态值的,可以找到每一次我们用的是什么面值的硬币。比如,从上面的图我们可以看出,最终结果d(11)=d(10)+1(面值为1),而d(10)=d(5)+1(面值为5),最后d(5)=d(0)+1(面值为5)。所以我们凑够11元最少需要的3枚硬币是:1元、5元、5元。 注意:原文中这里本来还有一段的,但我反反复复读了几遍,大概的意思我已经在上文从i=0到i=3的分析中有所体现了。作者本来想讲的通俗一些,结果没写好,反而更不好懂,所以这段不翻译了。 初级上面讨论了一个非常简单的例子。现在让我们来看看对于更复杂的问题,如何找到状态之间的转移方式(即找到状态转移方程)。为此我们要引入一个新词叫递推关系来将状态联系起来(说的还是状态转移方程) OK,上例子,看看它是如何工作的。 一个序列有N个数:A[1],A[2],…,A[N],求出最长非降子序列的长度。(讲DP基本都会讲到的一个问题LIS:longest increasing subsequence) 正如上面我们讲的,面对这样一个问题,我们首先要定义一个“状态”来代表它的子问题,并且找到它的解。注意,大部分情况下,某个状态只与它前面出现的状态有关,而独立于后面的状态。 让我们沿用“入门”一节里那道简单题的思路来一步步找到“状态”和“状态转移方程”。假如我们考虑求A[1],A[2],…,A[i]的最长非降子序列的长度,其中i d[i] = 1; for(int j=0; jlen) len = d[i]; } delete[] d; return len; } int main(){ int A[] = { 5, 3, 4, 8, 6, 7 }; cout |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |