数据结构与算法教程之动态规划（1）——动态规划入门

wzf2000
2019年10月20日

数据结构与算法教程之动态规划（1）——动态规划入门

Contents

动态规划

在学习之前

动态规划是什么

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。

这是百度百科的定义，当然听上去很牛啤。

但我们是学算法的，不是学算法历史的，所以这些并不重要。

动态规划，简称动规（dp），一般来说，是指设计状态以及转移，并且使得初始条件和结果的状态可表示，利用转移从初始条件推得结果的一种算法。（以上都是我瞎扯，忽略即可）

简单来说，动态规划最重要的是状态和转移。

动态规划的分类

根据百度百科，一般可分为线性动规，区域动规，树形动规，背包动规四类。

当然在每个大类中肯定还能有各种小类，比如背包 dp 就有九讲。（雾）

实际上，广义的动态规划几乎涵盖了大部分的算法，许多算法都是一种特殊的动态规划。

一般动态规划

虽然看起来是叫一般动态规划，但很多时候，最难的题也就是一般动态规划，所以千万不要觉得这是最简单的。

状态设计与转移

上面说过，动态规划最重要的是状态和转移，所以我们先来看看怎么设计。

一般状态设计是有要求的：

设计的状态可以覆盖所有可能性；
初始和结束都可以表示为有限个状态的运算；
设计的状态有确定有限的转移关系；
要尽量减少状态的复杂度与转移的复杂度；
希望状态可以有一个合理的便利顺序（暂时想到这些）

听上去还是跟没讲一样，所以我们直接看题。

第一题：最小路径和

给定一个包含非负整数的 $m \times n$ 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

保证 $n,m \le 1000$。

样例输入：

样例输出：

题解

这一题的关键是到右下角路径总和最小。

我们可以将状态拓宽一下：$dp[i][j]$ 表示走到 $(i,j)$ 时，最小的路径数字和。

因为 $(i,j)$ 只能从 $(i,j-1)$ 和 $(i-1,j)$ 走过来（不存在自动扔掉），所以转移也就是 $dp[i][j-1] \to dp[i][j],dp[i-1][j] \to dp[i][j]$。

具体来说我们可以得到转移方程 $dp[i][j]=\min(dp[i][j-1],dp[i-1][j])+a[i][j]$，$a[i][j]$ 表示 $(i,j)$ 上的数字。

初值只需要 $dp[1][1] = a[1][1]$。

而状态的顺序只要保证 $dp[i-1][j]$ 和 $dp[i][j-1]$ 在 $dp[i][j]$ 前被转移到。

故我们只需要 $i = 1 \sim n, j = 1 \sim m$ 即可。

程序主体部分大概会长这样：

dp[1][1]=a[1][1];
for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++)
    {
        if (i>1&&j>1) dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i][j];
        if (i>1&&j==1) dp[i][j]=dp[i-1][j]+a[i][j];
        if (i==1&&j>1) dp[i][j]=dp[i][j-1]+a[i][j];
    }
printf("%d\n",dp[n][m]);

分析

在这道题的解题过程中，我们会发现一个大致的思路：

首先构想一种可以用若干数表示的状态，符合上面的要求；
找到状态之间关系，并尝试写出其转移方程；
找到状态的初值和边界值；
找到状态的合适枚举顺序；
完成程序编写。

第二题：猴子跳台阶

一个顽猴在一座有 $n$ 级台阶的小山上爬山跳跃，猴子上山一步可跳 $x$ 级或跳 $y$ 级，试求猴子上山到 $n$ 级台阶有多少种不同的爬法？

猴子从山脚开始跳，可认为是第 $0$ 阶。

输入顺序为 $n,x,y$，保证 $x \le y \le n \le 100$。

样例输入：

3 1 2

样例输出：

样例解释：

$3 = 1 + 1 + 1 = 1 + 2 = 2+ 1$。

题解

同样道理，我们可以设计状态 $dp[i]$ 表示到达第 $i$ 级台阶有多少种不同方法。

那么很容易得到转移方程 $dp[i]=dp[i-x]+dp[i-y]$。

这里的顺序也只需要 $i=1 \sim n$，初值也就是 $dp[0] = 1$。

但是这样写出来的是错误的程序。

因为有 $x=y$ 的情况。

当然这种情况只需要特殊判断即可。

分析

这道题告诉了我们，我们要多考虑极端情况，对数据做到全覆盖。

绝对不能因为大多数情况下没错就认为是对的，一定要尽力排查各种特殊情况。

算法复杂度分析

在大多数动态规划的题目中，我们不仅需要正确的状态表示与转移，还需要尽量优的表示法。

那么如何判断一种状态表示的优劣呢？我们需要算法复杂度。

算法复杂度一般包括时间复杂度和空间复杂度。

时间复杂度可以认为是程序中进行基础运算次数的估算，而空间复杂度则是程序使用变量的占用内存大小估算。

因为很多时候不能对一个算法做到精确计算（考虑到实现的不同），我们这里的估算一般是用 $O$ 符号表示的数量级估算。

以上面两题为例：

第一题：时间复杂度 $O(nm)$，空间复杂度 $O(nm)$。

第二题：时间复杂度 $O(n)$，空间复杂度 $O(n)$。

注意第一题的 $n,m$ 大小同阶，故 $O(nm)$ 也可以表示为 $O(n^2)$。

空间上，我们可以根据大致的常数与复杂度的乘积估算占用内存。

时间上，在 $1s$ 内，一般认为以下数量级以及数据范围的对应较合适（需要根据实际代码常数进行调整）：

$O(n^4) \to n \le 100$
$O(n^3) \to n \le 400$
$O(n^2) \to n\le 5000$
$O(n \sqrt{n}) \to n \le 100000$
$O(n\log^2n) \to n\le 200000$
$O(n \log n) \to n \le 1000000$
$O(n) \to n \le 20000000$
$O(2^n) \to n \le 25$

总体来说大概就是，常数乘上复杂度不超过 $10^8$ 为佳。