动态规划把原问题时作若干个重叠子问题进行逐层递推求解，每个字问题的求解过程构成一个“阶段”。

1. 动态规划概念

动态规划算法的三要素：”状态“，”阶段“，”决策“。

动态规划求解的三个基本条件：”子问题重叠性“，“无后效行”，“最优子结构性质”。

无后效行：已求解的子问题不受后续阶段的影响。

最优子结构性质：下一阶段的最优解应该能够由前面各阶段字问题的最优解导出。

动态规划问题求解的的关键在于DP状态的表示和阶段的划分，并给出最终的状态转移方程、边界（或称为初始条件）和目标。

下面给出一些基本的经典问题。

2. 经典问题

最长上升子序列

描述

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

1
2
3
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

  • There may be more than one LIS combination, it is only necessary for you to return the length.
  • Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

分析

动态规划解法： $f[x]$ 表示是 $a[i]$ 为结尾的“最长上升子序列”的长度，也就是表示子数组 $a[1] … a[i]$ 的“最长上升子序列”的长度。以子序列的结尾位置进行阶段划分。则转移方程为
$$
f[i] = \max \limits_{0 \leq j<i, a[j]<a[i]} \{f[j]+1\}\
$$
边界 $f[0] = 0$ , 目标 $ \max \limits_{1 \leq i \leq N} \{ f[i]\}$。时间复杂度 $O(n^2)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// leetcode-300 注意与上述分析不同，代码中下标从0开始
int lengthOfLIS(vector<int>& a) {
    if (a.size() == 0) return 0;
    vector<int> f(a.size(), 1);  // 初始化为1
    int ans = 1;
    for (int i = 1; i < a.size(); ++i) {
        for (int j = 0; j < i; ++j) {
          	if (a[j] < a[i])
            f[i] = max(f[i], f[j]+1);
        }
      	ans = max(ans, f[i]);
    }
    return ans;
}

贪心+二分解法：虽然LIS是一道比较经典的动态规划题，但它还有其他更优的解法。从LIS的性质出发，要想得到一个更长的上升序列，该序列前面的数必须尽量的小。$a[i]$ 表示第 $i$ 个元素，$f[i]$ 表示长度为 $i$ 的LIS结尾元素的最小值。初始时 $f[1] = a[1]$， 从 $i = 2$ 时遍历原数列， 将每个遍历的数与 $f[]$ 的末尾进行比较；如果大于末尾， 将 $a[i]$ 放在 $f[]$ 数列的最后，$f[]$ 长度增加1， 如果小于末尾那么替换掉 $f[]$ 数列中大于等于 $a[i]$ 的第一个数。$f[]$ 最终的长度就是答案。时间复杂度 $O(nlogn)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lengthOfLIS(vector<int>& a) {
    if (a.size() == 0) return 0;
    vector<int> f;
    f.push_back(a[0]);
    for (int i = 1; i < a.size(); ++i) {
        if (a[i] > f.back())
          	f.push_back(a[i]);
        else {
            auto it = lower_bound(f.begin(), f.end(), a[i]);
            *it = a[i];
        }
    }
    return f.size();
}

扩展：输出任意最长上升子序列；输出所有最长上升子序列。

公共最长子序列

描述

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1:

1
2
3
Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

1
2
3
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

1
2
3
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

  • 1 <= text1.length <= 1000
  • 1 <= text2.length <= 1000
  • The input strings consist of lowercase English characters only.

分析

$f[i, j]$ 表示最长前缀子串 $a[1…i]$ 与$b[1…j]$ 的“最长公共子序列”的长度。则有如下转移方程
$$
f[i,j] =
\left\{
\begin{array}{**lr**}
max(f[i-1,j],\; f[i, j-1]), & a[i] \not= b[j]\\
f[i-1, j-1] + 1, & a[i] = b[j]
\end{array}
\right.
$$
边界条件 $f[i, 0] = f[j, 0] = 0$，目标 $f[n, m]$。时间复杂度$O(n^2)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int longestCommonSubsequence(string a, string b) {
    int n = a.size();
    int m = b.size();
    if (n == 0 || m == 0)
      	return 0;
    vector<vector<int>> f(n+1, vector<int>(m+1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i-1] == b[j-1])
              	f[i][j] = f[i-1][j-1] + 1;
            else
	              f[i][j] = max(f[i-1][j], f[i][j-1]);
        }
    }
    return f[n][m];
}

数字三角形

描述

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

1
2
3
4
5
6
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

分析

题目中说的是从上到下寻找一条路径，在实际的处理过程中可以选择一条从下到上的路径，这样处理的结果的等效的。状态转移方程如下
$$
f[i,j] = a[i,j]+min(f[i+1][j], \;f[i+1][j+1])
$$
初始条件 $f[n, j] = a[n, j]$，目标 $f[1, 1]$。

1
2
3
4
5
6
7
8
9
10
// leetcode 120. Triangle
int minimumTotal(vector<vector<int>>& triangle) {
    if (triangle.size() == 0) return 0;
    for (int i = triangle.size()-2; i >= 0; --i) {
        for (int j = 0; j < triangle[i].size(); ++j) {
          	triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
        }
    }
    return triangle[0][0];
}

最大子序列和

描述

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

1
2
3
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

分析

动态规划： $f[i]$ 表示以 $a[i]$ 结尾”最大子序和”。转移方程如下
$$
f[i] = max(f[i-1], \; 0) + a[i]
$$

1
2
3
4
5
6
7
8
9
10
11
int maxSubArray(vector<int>& nums) {
    if (nums.size() == 0) return 0;
    int maxNum = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i-1] > 0) {
          	nums[i] += nums[i-1];
        }
        maxNum = max(nums[i], maxNum);
    }
    return maxNum;
}

分治思想：假设 $f[i, j]$ 表示序列 $a[i…j]$ 的最大子序列和，$g[i, j]$ 表示序列 $a[i…j]$ 中以 $a[j]$ 结尾的最大子序列和，$h[i, j]$ 表示序列 $a[i…j]$ 中以 $a[i]$ 开头的最大子序列和。那么假设有 $k=(i+j)/2$ ，$a[i…j]$ 的最大子序列和有三种情况，在子序列 $a[i…k]$ 中，在子序列 $a[(k+1)…j]$ 中，或者横跨 $a[i…k]$ 和$a[(k+1)…j]$。则有公式：
$$
f[i, j] = max(f[i,k],\;f[k+1,j],\;g[i,k]+h[k+1,j])
$$
求解目标：$f[1,n]$，边界条件（初始条件）：$f[i,i] = g[i,i] = k[i,i] = a[i]$。

3. 状态的多维表示

上面的经典动态规划问题中状态打都是用一维或者二维数组表示的，这些问题中的DP状态表示方式还是比较简单。下面看一道多维状态表示和状态压缩的题目。

Mobile Service

描述​

链接：https://ac.nowcoder.com/acm/contest/1041/D
来源：牛客网

一个公司有三个移动服务员，最初分别在位置 1，2，3 处。 如果某个位置（用一个整数表示）有一个请求，那么公司必须指派某名员工赶到那个地方去。某一时刻只有一个员工能移动，且不允许在同样的位置出现两个员工。从 $p$ 到 $q$ 移动一个员工，需要花费 $c(p,q)$。这个函数不一定对称，但保证 $c(p,p)=0$。

给出N个请求，请求发生的位置分别为 $p_1\sim p_N$。公司必须按顺序依次满足所有请求，目标是最小化公司花费，请你帮忙计算这个最小花费。$N\leq 1000$，位置是 1~200 的整数。

分析

DP的阶段解释已经完成的请求数量。要计划花费就需要知道三个服务员的位置，那么状态就可以表示为$F[i, x, y, z]$，表示完成了前 $i$ 个请求，三个员工分别位于 $x, y, z$ 时，公司当前最小花费。状态转移如下：
$$
F[i+1][p_{i+1}][y][z] = min(F[i+1][p_{i+1}][y][z],\;F[i][x][y][z] + c(x, p_{i+1})) \\
F[i+1][x][p_{i+1}][z] = min(F[i+1][x][p_{i+1}][z],\;F[i][x][y][z] + c(y, p_{i+1})) \\
F[i+1][x][y][p_{i+1}] = min(F[i+1][x][y][p_{i+1}],\;F[i][x][y][z] + c(z, p_{i+1}))
$$
初始值：$F[0][1][2][3] = 0$ ，目标：$max\{F[n][?][?][?]\}$。

状态压缩：$ F[i][p_i][y][z]$ 在处理好第 $i$ 个请求之后，必有一个员工在位置 $p_i$。因此，状态可以缩小一维。

$F[i][x][y]$ 表示在处理好第 $i$ 个请求后，有一个员工在 $p_i$ 另外两个员工在 $x, y$ 时的最小花费。于是有状态转移如下：
$$
F[i+1][x][y] = min(F[i+1][x][y],\;F[i][x][y] + c(p[i], p[i+1])); //p[i+1] x y 互不相等\\
F[i+1][p_i][y] = min(F[i+1][p_i][y],\;F[i][x][y] + c(x, p[i+1])); //p[i+1] pi y 互不相等\\
F[i+1][x][p_i] = min(F[i+1][x][p_i],\;F[i][x][y] + c(y, p[i+1])); //p[i+1] pi x 互不相等
$$
初始值：$F[0][1][2] = 0$，令$p_0 = 3$，目标：$min\{F[n][?][?]\}$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int L = 206;
const int N = 1010;
int l, n;  // 位置数、请求数

int c[L][L];
int p[N];
int f[N][L][L];

const int INF = 0x3f3f3f3f;

bool check(int x, int y, int z) {
    if (x!=y && y!=z && z!=x)
        return true;
    return false;
}

int main(int argc, const char * argv[]) {
    memset(f, 0x3f, sizeof(f));

    scanf("%d%d", &l, &n);
    for (int i = 1; i <= l; ++i) {
        for (int j = 1; j <= l; ++j) {
            scanf("%d", &c[i][j]);
        }
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &p[i]);
    }

    f[0][1][2] = 0;
    p[0] = 3;
    for (int i = 0; i <= n-1; ++i) {
        for (int x = 1; x <= l; ++x) {
            for (int y = 1; y <= l; ++y) {
                if (f[i][x][y] != INF) {
                    if (check(p[i+1], x, y)) {
                        f[i+1][x][y] = min(f[i+1][x][y], f[i][x][y] + c[p[i]][p[i+1]]);
                    }
                    if (check(p[i+1], p[i], y)) {
                        f[i+1][p[i]][y] = min(f[i+1][p[i]][y], f[i][x][y] + c[x][p[i+1]]);
                    }
                    if (check(p[i+1], p[i], x)) {
                        f[i+1][x][p[i]] = min(f[i+1][x][p[i]], f[i][x][y] + c[y][p[i+1]]);
                    }
                }
            }
        }
    }
    int ans = 0x3f3f3f3f;
    for (int x = 1; x <= l; ++x) {
        for (int y = 1; y <= l; ++y) {
            ans = min(ans, f[n][x][y]);
        }
    }
    printf("%d\n", ans);
    return 0;
}