动态规划讲义

动态规划讲义

背景

动态规划（英语：Dynamicprogramming,简称DP）是一种在数

学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把

原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划不是某一种具体的算法，而是一种算法思想：若要解一个给

定问题，我们需要解其不同部分（即子问题），再根据子问题的解以

得出原问题的解。

问题引入：

P1744

小Q是一个宝石爱好者。

这一天，小Q来到了宝石古董店，店家觉得小Q是个宝石行家，于是决

定和小Q玩一个游戏。

游戏是这样的，一共有n块宝石，每块宝石在小Q心中都有其对应的价

值。注意，由于某些宝石质量过于差劲，因此存在只有店家倒贴钱，小Q才

愿意带走的宝石，即价值可以为负数。

小Q可以免费带走一个连续区间中的宝石，比如区间［1,3］或区间［2,4］

中的宝石。

请问小Q能带走的最大价值是多少？

问题分析

首先思考最暴力的解法。

枚举所有区间，暴力累加区间中宝石的价值，最后选一个价值最大的区间。

时间复杂度0（n八3）。

0（n八3）显然有些无法接受，因此想想有没有办法优化，比如优化掉暴力累

加的部分。

优化1.0

仔细思考不难发现，我们可以枚举区间右端点，然后固定右端点，左端点不

断向左移动，边移动边累加，就可以将时间复杂度优化到o（n八2）。

例如我们固定右端点是3,那么左端点就从3移动到1，边移动边累加答

案，就可以在移动过程中计算出区间［3,3］、［2,3］、［1,3］的答案了。因此

枚举所有区间右端点，即可在0（n八2）时间复杂度内找到答案。

但是0（n八2）时间还是有些过高了，因此思考有没有办法继续优化呢？

优化2.0

观察06人2）的解法，不难发现我们用了O（n）的时间复杂度才求出了固

定某个点为区间右端点时，区间最大价值和。

例如固定了n为区间右端点后，我们通过从n到1枚举左端点，才求

出了以n为区间右端点时的区间最大价值和，即O（n）的时间复杂度。

那么继续思考，「以n为区间右端点的区间最大和」，与「以n-1为

区间右端点的区间最大和」，这两者是否有关联呢？

为了描述方便，接下来我们用f[i]来代替「以i为区间右端点的区间最大

和」,用a[i]来代替第i块宝石的价值。

不难发现，如果f[n-1]为正数，则f[n]一定等于f[n-1]+a[n];如

果f[n-1]为负数，则f[n]一定等于a[n]o因此我们可以推导出如下转

移方程：

f[i]=max(f[i-1]+a[i],a[i])

根据上述转移方程，我们可以在02)时间复杂度内求出最大的f[i],即将

此题时间复杂度优化到0(n)，而这个优化的过程就是[■动态规划」的过程.

在上述推导过程中，一共分为两步：

1.将整个问题划分为一个个子问题，并令f[i]为第i个子问题的答案

2.思考大规模的子问题如何从小规模的子问题推导而来，即如何由f[i-1]

推出f[i]

这两个步骤便是「动态规划」解题思路的核心所在，即确定动态规划时的「状

态」与「转移方程」。

DP状态

[DP状态」的确定主要有两大原则：

1.最优子结构

2.无后效性

那怎样的状态定义算「有后效性」呢？

我们对「宝石挑选」例题增加一个限制，即小Q只能挑选长度〈二k的

连续区间。此时若我们定义f[i]表示「以i为右端点的长度＜=k的最

大连续区间和」，则f[i+1]的取值不仅取决于f[i]的数值，还取决于f[i]

是如何得到的。

因为如果f[i]取得最优值时区间长度二k,则f[i+1]不能从f[i]转移

得到，即f[i]的状杰定义有后效性。

最后概括一下，「最优子结构」就是「DP状态最优值由更小规模的DP状

态最优值推出」，此处DP状态即为子问题。而「无后效性」就是「无论DP

状态是如何得到的，都不会影响后续DP状态的取值」。

综上所述，我想我们对dp有个基本的了解了，要去解决一个dp

问题，最主要的就是去确定它的状态和状态转移方程

确定CDP状态」

符合「最优子结构」原则：DP状态最优值由更小规模的DP状态最优

值推出

符合「无后效性」原