深入浅出讲算法思想--动态规划思想分析及应用
动态规划：
这种算法思想多用来求解最优化问题，因此这里存在一个最优化法则，法则指出最优化问题任一实例的最优解，都是由其子实例的最优解构成的。一般来说，自底向上的动态规划更容易设计，但是带有记忆功能的自顶向下的动态规划跟能高效的解决问题（尤其是针对重叠子的问题）。
- 动态规划在求解硬币问题中的应用--币制最大化、找零问题、硬币收集问题
- 动态规划在求解背包问题中的应用--回溯法、记忆化法
- 动态规划在求解传递闭包问题中的应用--Warshell算法
- 动态规划在求解全源最短路径中的应用--Floyd算法
一、动态规划在求解硬币问题中的应用--币制最大化、找零问题、硬币收集问题
**1. 币值最大化问题：**给定一排n枚硬币，面值为正整数c1，c2，...，cn,面值可能相同，请问如何选取硬币，可以使得在其原始位置不相邻的条件下。所选币值总和最大。
思路：我们可以将问题划分为取最后一枚硬币和不取最后一枚硬币。根据不相邻这一条件，若取最后一枚硬币，则我们继续判断前n-2枚硬币中的币值总和最大问题；若不取最后一枚，则我们继续判断前n-1枚硬币中的币值总和最大问题。
由此得到递推方程如下，并且我们已知F(0) = 0，F(1) = c1,
Input:
5
5 1 2 10 6 2
Output:
17
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23import java.util.Scanner;
public class Main {
static int[] c = new int[10];
static int[] f = new int[10];
static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
int n = in.nextInt();
for (int i = 1; i <= n; i++) {
c[i] = in.nextInt();
}
System.out.println(coinRow(n));
}
private static int coinRow(int n) {
f[0] = 0;
f[1] = c[1];
for (int i = 2; i <= n; i++) {
f[i] = Math.max(c[i] + f[i-2], f[i-1]);
}
return f[n];
}
}
我们在这个过程中不仅得出了最大金额为17，我们在f[]中也可以求得前i枚硬币（1<=i<=6）的最大金额。时间复杂度和空间复杂度均为O(n)。
**2. 找零问题：**假设我们需要找零的金额为n，至少需要多少面值为d1<d2<...<dm的硬币？其中d1 = 1，且每种面值的硬币无限制。
思路：我们可以理解获得n的途径为：在总金额为n-dj的一堆硬币中在找一枚面值为dj的硬币，其中j=1,2，...,m，且n>=dj。因此找到一个满足要求的dj使得F(n-dj) + 1最小的dj即可。由于1是常量，所以我们需要专注寻找一个最小的F(d-dj)。
由此得到的递推公式如下，且一直F(0) = 0
Input:
6
1 3 4
Output:
2
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
30import java.util.Scanner;
public class Main {
static int[] c = new int[10];
static int[] f = new int[10];
static int sum;
static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
sum = in.nextInt();
int n = in.nextInt();
c[1] = 1;
for (int i = 2; i <= n; i++) {
c[i] = in.nextInt();
}
System.out.println(changeMaking(n));
}
private static int changeMaking(int n) {
for (int i = 1; i <= sum; i++) {
int temp = 99999999;
int j = 1;
while (j <= n && i >= c[j]) {
temp = Math.min(f[i-c[j]], temp);
j++;
}
f[i] = temp +1;
}
return f[sum];
}
}
**3. 硬币收集问题：*在nm格模板中放有一些硬币，每格的硬币数目最多为一个。从左上方开始收集，尽可能收集多的硬币直到右下角对于每个单元格来说，只能取对应右边一格或者下边一格的硬币。试求出最大的硬币数及相应的路径。思路：我们假设F(i, j)为行走到(i, j)所能收集到的最大硬币数。单元格(i, j)可以经由上方(i-1, j)和左侧单元格(i, j-1)到达。单元格(i-1 ,j)对应的最大硬币数为F(i-1, j)，(i, j-1)对应的最大硬币数为F(i, j - 1)。当然，第一行单元格上方没有单元格，第一列单元格左边没有单元格，即F(i-1, j) = 0，F(i, j-1) = 0，所以其递推公式为：
Input:
5 6
0 0 0 0 1 0
0 1 0 1 0 0
0 0 0 1 0 1
0 0 1 0 0 1
1 0 0 0 1 0
Output:
5
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
46import java.util.Scanner;
public class Main {
static int[][] c = new int[10][10];
static int[][] f = new int[10][10];
static int sum, n, m;
static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
n = in.nextInt();
m = in.nextInt();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
c[i][j] = in.nextInt();
}
}
f[1][1] = c[1][1];
System.out.println(coinCollection());
}
private static int coinCollection() {
/**
* 左上角，初始位置
* */
f[1][1] = c[1][1];
/**
* 第一列只有上方来的
* */
for (int i = 2; i <= n; i++) {
f[i][1] += f[i-1][1];
}
/**
* 第一行只有左侧来的
* */
for (int j = 2; j <= m; j++) {
f[1][j] += f[1][j-1];
}
for (int i = 2; i <= n; i++) {
for (int j = 2; j <= m; j++) {
f[i][j] = Math.max(f[i-1][j], f[i][j-1]) + c[i][j];
}
}
return f[n][m];
}
}
二、动态规划在求解背包问题中的应用--回溯法、记忆化法
背包问题向来是动态规划的典型问题，给定n个重量为w1,w2,...,wn，价值为v1,v2,...,vn的物品和一个称重量为W的背包，求这些物品中最优价值的一个子集，且能够装到背包中。
之前文章深入浅出讲算法思想--蛮力法思想分析及应用的第六部分有用蛮力法解决背包问题的思路。
这篇文章将采用动态规划思想解决，在解题之前，我们首先要推导出一个关系，用较小子实例的解来表示背包问题整体实例的解。我们先来考虑前i个物品（1<=i<=n）定义的实例，物品重量分别为w1,w2,...,wi，价值分别为v1,v2,...,vi，背包承重量为j（1<=j<=W）。设F(i, j)表示该实例的最优解的物品总价值，那么对于这样一个实例，我们可以分为不取第i个物品和取第i个物品两种情况，如果不取第i个物品，那么最优子集的价值为F(i-1, j)；如果取第i个物品，那么总价值为vi+前i-1个物品点1最大价值F(i-1, j-wi)。由此我们得出下面的递推公式：
我们还可以知道初始条件：
当j>=0时，F(0, j) = 0； 当i >= 0时，F(i, 0) = 0
回溯解法：
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
31import java.util.Scanner;
public class Main {
static int[] w = new int[10];
static int[] v = new int[10];
static int n, W;
static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
n = in.nextInt();
W = in.nextInt();
for (int i = 1; i <= n; i++) {
w[i] = in.nextInt();
v[i] = in.nextInt();
}
System.out.println(f(n, W));
}
private static int f(int n, int W) {
if(n == 0 || W == 0){
return 0;
}
for(int i = n;i >=0; i--) {
if(w[i] > W) {
return f(n-1, W);
} else {
return Math.max(f(n-1, W), f(n-1, W-w[i])+v[i]);
}
}
return 0;
}
}
记忆化求解：
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
36import java.util.Scanner;
public class Main {
static int[] w = new int[10];
static int[] v = new int[10];
static int[][] f = new int[10][10];
static int n, W;
static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
n = in.nextInt();
W = in.nextInt();
for (int i = 0; i < f.length; i++) {
for (int j = 0; j < f[0].length; j++) {
f[i][j] = 0;
}
}
for (int i = 1; i <= n; i++) {
w[i] = in.nextInt();
v[i] = in.nextInt();
}
System.out.println(f(n, W));
}
private static int f(int i, int j) {
int temp;
if(f[i][j] <= 0 && i>0) {
if (j < w[i]) {
temp = f(i-1, j);
} else {
temp = Math.max(f(i-1, j), v[i] + f(i-1, j - w[i]));
}
f[i][j] = temp;
}
return f[i][j];
}
}
由于DP问题经常有重叠子的计算问题，所以自顶向下的记忆化DP方法要优于自底向上的回溯算法。
滚动数组：
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
30import java.util.Scanner;
public class Main {
static int maxV, maxM, n;
static int[] v,k;
static int[] f;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
maxV = in.nextInt();
maxM = in.nextInt();
f = new int[maxV + 1];
n = in.nextInt();
v = new int[n + 1];
k = new int[n + 1];
for (int i = 1; i <= n; i++) {
v[i] = in.nextInt();
k[i] = in.nextInt();
}
for (int i = 1; i <= n; i++) {
for (int j = maxV; j >= 0; j--) {
for (int s = maxM; s >= 0; s--) {
if (j >= v[i] ) {
f[j] = Math.max(f[j-v[i]] + k[i], f[j]);
}
}
}
}
System.out.println(f[maxV]);
}
}
三、动态规划在求解传递闭包问题中的应用--Warshell算法
**传递闭包：**对于n个顶点有向图来说，如果第i个顶点到第j个顶点之间存在一条有效的有向路径（即长度大于0的路径），那么T(i, j) = 1,否则T(i, j) = 0。例如：
求解传递闭包我们可以使用深度优先搜索和广度优先搜索，我们可以对每个顶点进行DFS/BFS，在对应的矩阵位置上置为1，遍历之后我们便得到整个图的传递闭包。
但是这种方式并不是高效的算法，而Warshell算法却能很好的解决问题。
Warshell算法通过一系列n阶布尔矩阵来构造传递闭包 R(0),...R(k),...,R(n) 。其中的每个布尔矩阵都提供有向图中有向路径的特定信息。具体来说，当且仅当从第i个顶点到第j个顶点之间存在一条有向路径，并且路径的每一个中间顶点的编号不大于k时，矩阵中第i行第j列的元素值为1。
R(0)中每个点的含义为：当且仅当从第i个顶点到第j个顶点之间存在一条有向路径，并且路径不存在中间顶点。即该矩阵为图的邻接矩阵。
R(k)中每个点的含义为：当且仅当从第i个顶点到第j个顶点之间存在一条有向路径，并且路径的每一个中间顶点的编号不大于k
R(n)中每个点的含义为：当且仅当从第i个顶点到第j个顶点之间存在一条有向路径，并且路径的每一个中间顶点的编号不大于n，即图的传递闭包。
思路：任何R(k)可以由R(k-1)计算的到的，那么，从第i个顶点vi到第j个顶点vj的路径可以表示为：
vi, ]每个顶点编号<=k的一个中间顶点集]，vj
这会存在两种情况，情况一：R(k-1) = 1，中间顶点集中不包含k即可到达vj;
情况二，R(k-1) = 0，中间顶点集必须包含k才能到达vj，那么，只有当矩阵中第i行第k列的元素和第k行第j列的元素都是1，R(k)才能是1。示例如下图：
下面将以示例的形式具体展示Warshell算法的流程：
Input：
4 4 1 2 2 4 4 1 4 3
Output:
1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1
完整代码如下：
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
37import java.util.Scanner;
public class Main {
static int[][] e = new int[10][10];
static int n, m;
static Scanner input = new Scanner(System.in);
public static void main(String[] args) {
n = input.nextInt();
m = input.nextInt();
for (int i = 1; i <= m; i++) {
int a = input.nextInt();
int b = input.nextInt();
e[a][b] = 1;
}
floyd();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
System.out.print(e[i][j] + " ");
}
System.out.println();
}
}
public static void floyd() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (e[i][j] != 0) {
e[i][j] = 1;
} else if (e[i][k]!=0 && e[k][j]!=0) {
e[i][j] = 1;
}
}
}
}
}
}
时间复杂度：O(n^3)
更一般的问题是求解带权图中全源最短路径的长度。
四、动态规划在求解全源最短路径中的应用--Floyd算法
不熟悉这种算法的读者可以参考图论算法(二)--最短路径的Dijkstra [ 单源 ] 和Floyd[ 多源 ] 解法(JAVA)
这种算法也叫Floyd-Warshell算法，虽然和Warshell算法名字相近，算法思想也相近，但确实是两种算法。 对于一个带权图（无向或有向），全源最短路径问题就是找出每个顶点到其他所有顶点之间的最短距离。我们用一个n阶距离矩阵来记录最短路径的长度。需要注意的是该算法不适合带负权的回路图。
那么对于任意i到j的路径可以表示为：vi, 顶点标号不大于k的一个中间顶点集，vj
我们在把这种路径分成两个不相交的情况，
情况一：子集中不将第k个顶点作为中间顶点。在这种情况下，路径所包含的中间顶点的编号都不大于k-1；
情况二：子集中不将第k个顶点作为中间顶点。在这种情况下，顶点vk在中间顶点中，且出现过一次。
上述两种情况可以由下图表示：
下面是一个实例用来展示算法的过程：
Input:
4 5 1 3 3 2 1 2 3 2 7 4 1 6 3 4 1
Output:
0 10 3 4 2 0 5 6 7 7 0 1 6 16 9 0
完整代码如下：
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
45import java.util.Scanner;
public class minPath {
static int[][] e = new int[10][10];
static int n, m;
static Scanner input = new Scanner(System.in);
public static void main(String[] args) {
n = input.nextInt();
m = input.nextInt();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i == j) {
e[i][j] = 0;
} else {
e[i][j] = 99999999;
}
}
}
for (int i = 1; i <= m; i++) {
int a = input.nextInt();
int b = input.nextInt();
int c = input.nextInt();
e[a][b] = c;
}
floyd();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
System.out.print(e[i][j] + " ");
}
System.out.println();
}
}
public static void floyd() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (e[i][j] > e[i][k] + e[k][j]) {
e[i][j] = e[i][k] + e[k][j];
}
}
}
}
}
}