动态规划前瞻

发表于 | 分类于 | 阅读次数:

Those who cannot remember the past are condemned to repeat it.
-Dynamic Programming.

动态规划

定义

动态规划（dynamic programming）是通过组合子问题而解决整个问题的解。 分治法是将问题划分成一些独立的子问题，递归地求解各子问题，然后合并子问题的解。 动态规划适用于子问题不是独立的情况，也就是各子问题包含公共的子子问题。
此时，分治法会做许多不必要的工作，即重复地求解公共的子问题。动态规划算法对每个子问题只求解一次，将其结果保存起来，从而避免每次遇到各个子问题时重新计算答案。

适用范围

最优性原理体现为问题的最优子结构特性。当一个问题的最优解中包含了子问题的最优解时，则称该问题具有最优子结构特性。
最优性原理是动态规划的基础。任何一个问题，如果失去了这个最优性原理的支持，就不可能用动态规划设计求解。

  • 问题中的状态满足最优性原理。
  • 问题中的状态必须满足无后效性。

所谓无后效性是指：“下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前状态是对以往决策的总结”。

首先，动态规划方法适合的题型4个基本特点是：

  1. 最优子结构，当前一个状态得到最佳解时，当前状态在前一个状态下一定有最佳解；
  2. 子问题重叠，每个状态下要解决的问题除参数不同外，其本质是一样的；
  3. 有边界，当解决了最后一个子问题时，整个问题得解；
  4. 子问题独立，解决一个子问题时不依赖于另一个同级的子问题，只与它的母问题有关。

动态规划的设计

两种方法：

  • 自顶向下（又称记忆化搜索、备忘录）：基本上对应着递归函数实现，从大范围开始计算，要注意不断保存中间结果，避免重复计算
  • 自底向上（递推）：从小范围递推计算到大范围

一般分为两个步骤：

  1. 问题建模
  2. 求解问题

核心元素

有三个核心元素：

  1. 最优子结构
  2. 边界
  3. 状态转移方程

总结DP算法的思路

核心: 最优子结构、边界条件、状态转移方程

解题步骤: 1.建立数学模型 2.写代码求解问题

如何建模?先写出所求问题的最优子结构,进而分析出边界和状态转移方程，数学模型即这2者的组合，对于2输入维度动态规划，画表格帮助分析，行列分别代表1个输入维度

如何求解?
建好模后，根据方程组写出自底向上的动态规划代码，一维输入就是1个for循环，二维输入就是2个for循环，如果方程组比较抽象，可以画表格帮助分析

棋盘问题

问题

寻找一条从左上角（arr[0][0]）到右下角（arr[m - 1][n - 1]）的路线，使得沿途经过的数组中的整数和最小。

递归算法

从右下角倒着分析，最后一步到达arr[m - 1][n - 1]只有两条路径，即通过arr[m - 2][n - 1]或arr[m - 1][n - 2]到达。
推广到一半的情况，假设到达arr[i - 1][j]与arr[i][j - 1]的最短路径的和为f(i - 1, j)和f(i, j - 1)，那么到达arr[i][j]的路径上所有数字和的最小值为 f(i, j) = min{f(i - 1, j), f(i, j - 1)} + arr[i][j]

递归方法实现效率太低，有大量重复计算过程。

动态规划算法

动态规划其实是一种空间换时间的算法，通过缓存计算的中间值，减少重复计算的次数，从而提高算法的效率。
递归从arr[m - 1][n - 1]开始逆向通过递归来求解，采用动态规划可以自底向上求解，以便使用前面计算出来的结果。
对于本题而言，显然有边界条件，f(i, 0) = arr[0][0] + arr[i][0]， f(0, j) = arr[0][0] + arr[0][j]。
状态转移方程： f(i, j) = min{f(i - 1, j), f(i, j - 1)} + arr[i][j]

可以把遍历过程中求出所有的f(i, j)的值，保存到另一个二维数组中供后续使用。

数组和最小的路线
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
public class Test {
	public static int getMinPath() {
		if (arr == null || arr.lenth == 0)
			return 0;
		int row = arr.length;
		int col = arr[0].length;
		int[][] cache = new int[row][col];

		for (int i = 1; i < row; i++)
			cache[i][0] = cache[i-1][0] + arr[i][0];
		for (int j = 1; j < col; j++)
			cache[0][j] = cache[0][j-1] + arr[0][j];

		for (int i = 1; i < row; i++) {
			for (int j = 1; j < col; j++) {
				//可以确定选择的路线为arr[i-1][j]
				if (arr[i-1][j] < arr[i][j-1]) {
					cache[i][j] = cache[i-1][j] + arr[i][j];
					System.out.print("[" + (i - 1) + ", " + j + "] ");
				} else {
					cache[i][j] = cache[i][j-1] + arr[i][j];
					System.out.print("[" + i + ", " + (j - 1) + "] ");
				}
			}
		}
		System.out.println("[" + (row - 1) + ", " + (col - 1) + "]");
		return cache[row - 1][col - 1];
	}

	public static void main(String[] args) {
		int[][] arr = {{1,4,3}, {8,7,5}, {2,1,5}};
		System.out.print("路径： ")；
		System.out.println("最小值为： " + getMinPath(arr));
	}
}

对二维数组遍历一次，时间复杂度为O(mn)，申请了一个二维数组来保存中间结果，空间复杂度为O(mn)。

国王与金矿

知道 i-1 座金矿的最大产量就一定能知道 i 座金矿的最大产量，这是 最优子结构，每个人要知道i座金矿的最大产量就必须知道知道 i-1 座金矿的最大产量，这是 子问题重叠，最终当考虑第 1 座金矿的最大产量时，只要看是否有足够人手开采第 1 座金矿，有的话，答案是已探明的储量，没有的话就是0，然后答案汇报到上级，上级再得出第 2 座金矿开采与不开采得出的较大产量，再往上汇报…，这就是 边界，而每个人从上级得到的前提都是不同的，上级决定开不开采，再将这个前提之一告诉下属，而下属不需要考虑上级给另一个下属什么前提，这是 子问题独立。

把金矿数量设为n，工人数量设为w，金矿的黄金量设为g[]，金矿的用工量设为p[]。
F(n, w) = 0 (n <= 1, w < p[0]);
F(n, w) = g[0] (n == 1, w >= p[0]);
F(n, w) = F(n - 1, w) (n > 1, w < p[n - 1]);
F(n, w) = max(F(n - 1, w)， F(n - 1, w - p[n - 1]) + g[n - 1]) (n > 1, w >= p[n-1]);

递归算法

把状态转移方程翻译成递归程序，递归结束条件是方程中的边界。 因为每个状态有两个最优子结构，所以递归的执行流程类似于一棵高度为N的二叉树。 时间复杂度为O(2^n)。

递归解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int getMostGold(int n, int w, int[] g, int[] p) {	
    if (n > g.length)
        throw new RuntimeException("输入的n值大于给定的金矿数");
      
    if (n <= 1 && w < p[0]) 
        return 0;
    
    if (n == 1 && w >= p[0])
        return g[0];
 
    if (n > 1 && w < p[n-1]) 
        return getMostGold(n-1, w, g, p);
     
    int a = getMostGold(n-1, w, g, p);
    int b = getMostGold(n-1, w - p[n-1], g, p) + g[n-1];
    return Math.max(a, b);
         
}

DP解法

画表格分析，表格第一列代表给定前1-5做金矿的情况，也就是N的取值。表格第一行代表给定的工人数，也就是w的取值。
其余空白格表示，给定n和w值对应的黄金获得数，也就是F(n,w)。

1工人 2工人 3工人 4工人 5工人 6工人 7工人 8工人 9工人 10工人
1金矿
2金矿
3金矿
4金矿
5金矿

第一个金矿的信息：400金，5工人

1工人 2工人 3工人 4工人 5工人 6工人 7工人 8工人 9工人 10工人
1金矿 0 0 0 0 400 400 400 400 400 400
2金矿
3金矿
4金矿
5金矿

第二个金矿的信息：500金，5工人
根据F(n,w) = Max(F(n-1, w), F(n-1, w-5) + 500)， 5-9格子为500，第2行第10个格子，n=2，w=10 F(n-1, w-5) = 400 Max(400, 400+500) = 900

1工人 2工人 3工人 4工人 5工人 6工人 7工人 8工人 9工人 10工人
1金矿 0 0 0 0 400 400 400 400 400 400
2金矿 0 0 0 0 500 500 500 500 500 900
3金矿
4金矿
5金矿

第三个金矿的信息：200金，3工人

根据F(n,w) = Max(F(n-1, w), F(n-1, w-5) + 200)

1工人 2工人 3工人 4工人 5工人 6工人 7工人 8工人 9工人 10工人
1金矿 0 0 0 0 400 400 400 400 400 400
2金矿 0 0 0 0 500 500 500 500 500 900
3金矿 0 0 200 200 500 500 500 700 700 900
4金矿
5金矿

第四个金矿的信息：300金，4工人

根据F(n,w) = Max(F(n-1, w), F(n-1, w-5) + 300)

1工人 2工人 3工人 4工人 5工人 6工人 7工人 8工人 9工人 10工人
1金矿 0 0 0 0 400 400 400 400 400 400
2金矿 0 0 0 0 500 500 500 500 500 900
3金矿 0 0 200 200 500 500 500 700 700 900
4金矿 0 0 200 300 500 500 500 700 800 900
5金矿

第五个金矿的信息：350金，3工人

根据F(n,w) = Max(F(n-1, w), F(n-1, w-5) + 350)

1工人 2工人 3工人 4工人 5工人 6工人 7工人 8工人 9工人 10工人
1金矿 0 0 0 0 400 400 400 400 400 400
2金矿 0 0 0 0 500 500 500 500 500 900
3金矿 0 0 200 200 500 500 500 700 700 900
4金矿 0 0 200 300 500 500 500 700 800 900
5金矿 0 0 350 350 500 550 650 850 850 900

上述表格，比如5金矿10工人的结果，来自于4金矿7工人和4金矿10工人， Max(900, 500+350)=900

不需要存储整个表格，只需要存储前一行的结果，就可以推导出新的一行。使用动态规划如下：

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int getMostGold(int n, int w, int[] g, int[] p) {
	if (n > g.length)
		throw new RuntimeException("输入的n值大于给定的金矿数")；
	if (w < 0)
		throw new RuntimeException("输入的工人数w不能为负数")；
	if (n < 1 || w == 0) 
		reurn 0;

	int col = w + 1;
	int[] preResults = new in[col];
	int[] results = new int[col];

	//填充边界格子的值 (边界)
	for (int i = 0; i < col; i++) {
		if (i < p[0]) {
			preResults[i] = 0;
		} else {
			preResults[i] = g[0];
		}
	}

	if (n == 1) {
		return preResults = g[0];
	}

	//填充其余格子的值，外层循环是金矿的数量(递推的轮次)，内层循环是工人数
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < col; j++) {
			if (j < p[1]) {
				results[j] = preResults[j];
			} else {
				results[j] = Math.max(preResults[j], reResults[j-p[i]] + g[i]);
			}
		}
		for (int j = 0; j < col; j++) {
			//更新上一行的值，为下一轮递推做准备
			preResults[j] = results[j];
		}
		/* preResults = results;
		* 这样赋值会导致preResults和results指向同一个数组，
		*在下一轮循环中改变results中的值也改变了preResults中的值
		*/
	}
	return results[w];
}

上述方法利用两层迭代，外层迭代对表格每一行的迭代过程中，会保留上一行的结果数组preResults，并循环计算当前的结果数组results。
方法的时间复杂度为O(n*w)，空间复杂度是O(w)。
当金矿更多的时候，动态规划的优势就能体现出来。

然而，当工人为1000时，动态规划的时间复杂度为5 * 1000 = 5000，开辟1000单位的空间。 递归的时间复杂度是O(2^n)，需要计算32次，开辟5单位（递归深度）的空间。

动态规划方法的时间和空间都和w成正比，而简单递归和w无关，所以工人很多的时候，动规反而不如递归。

所以说，每一种算法都没有绝对的好与坏，关键看应用场景。

备忘录解法

备忘录解法 
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// 该内部类对象用于备忘录算法中作为HashMap存储的键
private static class Input {
	private int n;
	private int w;

	public Input(int n, int w) {
		super();
		this.n = n;
		this.w = w;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + n;
		result = prime * result + w;
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Input other = (Input) obj;
		if (n != other.n)
			return false;
		if (w != other.w)
			return false;
		return true;
	}

}

	// 备忘录算法解法
public static int getMostGold2(int n, int w, HashMap<Input, Integer> map, int[] g, int[] p) {
    if (n > g.length) 
        throw new RuntimeException("输入的n值大于给定的金矿数");
    
    if (n <= 1 && w < p[0]) 
        return 0;
    
    if (n == 1 && w >= p[0])
        return g[0];

    if (n > 1 && w < p[n-1]) {
        Input input = new Input(n-1, w);
        if (map.containsKey(input)) 
            return map.get(input);
        
        int value = getMostGold2(n-1, w, map, g, p);
        map.put(input, value);
        return value;
    }
        
   Input input1 = new Input(n-1, w);
   Input input2 = new Input(n-1, w-p[n-1]);
   int a = 0; //用于记录F(n-1,w)的值
   int b = 0; //用于记录F(n-1,w-p[n-1])+g[n-1])的值

   if (map.containsKey(input1)) 
       a = map.get(input1);
   a = getMostGold2(n-1, w, map, g, p);
   map.put(input1, a);
   
   if (map.containsKey(input2)) 
       b = map.get(input2) + g[n-1];
   b = getMostGold2(n-1, w-p[n-1], map, g, p);
   map.put(input2, b);
   b += g[n-1];

  return a > b ? a : b;
}
0%