动态规划算法学习

问题及分析：

一种平衡的0-1矩阵  

考虑n *n 矩阵的赋值问题：只能赋0和1，n 为偶数，使每一行和列均含n /2个0及n /2个1。例如，当n =4时，两种可能的方案是：

+ - - - - +             + - - - - +
| 0 1 0 1 |             | 0 0 1 1 |
| 1 0 1 0 |             | 0 0 1 1 |
| 0 1 0 1 |             | 1 1 0 0 |
| 1 0 1 0 |             | 1 1 0 0 |
+ - - - - +             + - - - - +

问：对于给定n ，共有多少种不同的赋值方案。

至少有三种可能的算法来解决这一问题：穷举法（brute force）、回溯法（backtracking）及动态规划（dynamic programming）。穷举法列举所有赋值方案，并逐一找出满足平衡条件的方案。由于共有C(n , n /2)^n 种方案（在一行中，含n/2个0及n/2个1的组合数为C(n,n/2)，相当于从n个位置中选取n/2个位置置0，剩下的自然是1 ），当n =6时，穷举法就已经几乎不可行了。回溯法先将矩阵中部分元素置为0或1，然后检查每一行和列中未被赋值的元素并赋值，使其满足每一行和列中0和1的数量均为n /2。回溯法比穷举法更加巧妙一些，但仍需遍历所有解才能确定解的数目，可以看到，当n =8时，该题解的数目已经高达116963796250。动态规划则无需遍历所有解便可确定解的数目（意思是划分子问题后，可有效避免若干子问题的重复计算 ）。

通过动态规划求解该问题出乎意料的简单。考虑每一行恰含n /2个0和n /2个1的k *n (1<=k <=n )的子矩阵，函数f根据每一行的可能的赋值映射为一个向量，每个向量由n 个整数对构成。向量每一列对应的一个整数对中的两个整数分别表示该列上该行以下已经放置的0和1的数量。该问题即转化为寻找f((n /2,n /2),(n /2,n /2),...,(n /2,n /2))（具有n 个参数或者说是一个含n 个元素的向量）的值。其子问题的构造过程如下：

1) 最上面一行（第k行 ）具有C(n , n /2)种赋值；

2) 根据最上面一行中每一列的赋值情况（为0或1），将其对应整数对中相应的元素值减1；

3) 如果任一整数对中的任一元素为负，则该赋值非法，不能成为正确解；

4) 否则，完成对k *n 的子矩阵中最上面一行的赋值，取k =k -1，计算剩余的(k -1)*n 的子矩阵的赋值；

5) 基本情况是一个1*n 的细小的子问题，此时，该子问题的解的数量为0或1，取决于其向量是否是n /2个(0, 1)和n /2个(1, 0)的排列。

例如，在上面给出的两种方案中，向量序列为：

((2, 2) (2, 2) (2, 2) (2, 2))       ((2, 2) (2, 2) (2, 2) (2, 2))     k = 4
  0      1      0      1              0       0       1      1

((1, 2) (2, 1) (1, 2) (2, 1))       ((1, 2) (1, 2) (2, 1) (2, 1))     k = 3
  1      0      1      0              0      0      1      1

((1, 1) (1, 1) (1, 1) (1, 1))       ((0, 2) (0, 2) (2, 0) (2, 0))     k = 2
  0      1      0      1              1      1      0      0

((0, 1) (1, 0) (0, 1) (1, 0))       ((0, 1) (0, 1) (1, 0) (1, 0))     k = 1
  1      0      1      0              1      1      0      0

((0, 0) (0, 0) (0, 0) (0, 0))       ((0, 0) (0, 0), (0, 0) (0, 0))

动态规划在此的意义在于避免了相同f的重复计算，更进一步的，上面着色的两个f，虽然对应向量不同，但f的值是相同的，想想为什么吧 :D。

该问题解的数量（序列a058527在OEIS）是1, 2, 90, 297200, 116963796250, 6736218287430460752, ...

 

实现：

import java.util.HashMap;
import java.util.Map;

public class DynamicPrograming {
	private static Map<String, Long> map = new HashMap<String, Long>();
	private static String acceptKey = null;

	public static void main(String[] args) {
		long result = DynamicPrograming.f(10);
		System.out.println(result);
	}

	private static void init(int n) {
		if(n % 2 != 0) {
			System.err.println("n必须为2的倍数");
			System.exit(0);
		}
		acceptKey = "";
		for (int i = 0; i < n; i++) {
			acceptKey += "00";
		}
	}

	public static long f(int n) {
		init(n);
		int[][] arr = new int[n][2];
		for (int i = 0; i < n; i++) {
			arr[i][0] = n / 2;
			arr[i][1] = n / 2;
		}
		return y(arr, n);
	}

	public static long y(int[][] arr, int n) {
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[i].length; j++) {
				if (arr[i][j] < 0) {
					return 0;
				}
			}
		}

		String key = calculateKey(arr);
		if (key.contains("-1")) {
			return 0;
		} else if (key.equals(acceptKey)) {
			return 1;
		}

		long result = 0;
		if (map.get(key) == null) {
			int[] solution = new int[n];
			for (int i = 0; i < n / 2; i++) {
				solution[i] = 1;
			}
			int[][] arrCopy = buildParam(solution, arr);
			result += y(arrCopy, n);
			boolean isFinished = false;
			while (true) {
				for (int i = n / 2; i < n; i++) {
					if (solution[i] != 1) {
						isFinished = false;
						break;
					}
					isFinished = true;
				}
				if (isFinished) {
					map.put(calculateKey(arr), result);
					return result;
				}
				// 遍历每行所有的可能结果
				// 从右往左找到第一个可以往右移动的1，移动一个位移，记录下标，再从该下标起左往右扫描，将所有1紧挨着排列
				for (int i = n - 2; i >= 0; i--) {
					if (solution[i] == 1 && solution[i + 1] == 0) {
						solution[i] = 0;
						solution[i + 1] = 1;
						int x = i + 1;
						for (int j = x + 1; j < n; j++) {
							if (solution[j] == 1) {
								solution[j] = 0;
								solution[x + 1] = 1;
								x++;
							}
						}
						break;
					}
				}
				// 计算下一行函数的参数
				arrCopy = buildParam(solution, arr);
				result += y(arrCopy, n);
			}
		} else {
			return map.get(key);
		}
	}

	private static int[][] buildParam(int[] solution, int[][] arr) {
		int[][] arrRet = arr.clone();
		for (int i = 0; i < solution.length; i++) {
			arrRet[i] = arr[i].clone();
			if (solution[i] == 0) {
				arrRet[i][0] -= 1;
			} else {
				arrRet[i][1] -= 1;
			}
		}
		return arrRet;
	}

	private static String calculateKey(int[][] arr) {
		int[][] arrcopy = new int[arr.length][2];
		if (arr[0][0] > arr[1][0]
				|| (arr[0][0] == arr[1][0] && arr[0][1] >= arr[1][1])) {
			arrcopy[0] = arr[0].clone();
			arrcopy[1] = arr[1].clone();
		} else {
			arrcopy[0] = arr[1].clone();
			arrcopy[1] = arr[0].clone();
		}
		int n = 1;
		for (int i = 2; i < arr.length; i++) {
			if (arr[i][0] < arrcopy[n][0]
					|| (arr[i][0] == arrcopy[n][0] && arr[i][1] <= arrcopy[n][1])) {
				arrcopy[++n] = arr[i].clone();
				continue;
			}
			for (int j = 0; j <= n; j++) {
				if (arr[i][0] > arrcopy[j][0]
						|| (arr[i][0] == arrcopy[j][0] && arr[i][1] >= arrcopy[j][1])) {
					for (int k = n; k >= j; k--) {
						arrcopy[k + 1] = arrcopy[k];
					}
					arrcopy[j] = arr[i].clone();
					n++;
					break;
				}
			}
		}
		String result = "";
		for (int i = 0; i < arrcopy.length; i++) {
			for (int j = 0; j < arrcopy[i].length; j++) {
				result = result + arrcopy[i][j];
			}
		}
		return result;
	}
}

 

 

动态规划重在问题分析，将问题划分为子问题直到可以容易的求解，并添加缓存避免重复计算。