动态规划算法学习 博客分类： 算法 java算法动态规划粉刷algorithm

给定待粉刷的n个墙砖(排成一行)，每个墙砖可以粉刷的颜色种类为:红、蓝、绿、黄，问粉刷完毕后，红色墙砖和蓝色墙砖都是偶数的粉刷方式有多少种(结果对10007取余).

题目解析：
首先题目问红色和蓝色都是偶数的粉刷方式，由此可以得出，其他的刷黄刷绿无所谓，都可以。因此可以把颜色分为红，蓝，其它。
题目只关注奇偶，不关注具体红蓝各刷了多少块，因此我们也只分奇偶即可。
很显然前面n-1块砖的粉刷方式会对第n次粉刷的结果产生影响，由此我想这应该是一个动态规划问题。
第n块粉刷后的结果取决于第n-1块的结果，第n-1块的结果取决于n-2,... ... ， 第2块的粉刷结果取决于第1块的结果。
只刷一块可能的粉刷方式是：
1》刷一块绿或黄，这样红，蓝都是偶数；两种刷法，刷绿，刷黄；
结果为2；
此时考虑粉刷2块的情况：
当第一块刷按方式1》刷时，为了得到偶数红蓝，第二块只能刷绿黄， 所以有四种刷法；
但这并不是最终结果，因为可以刷两块红，也是正解；
第二块的结果还依赖于第一块的非正确结果，我们分析只刷一块的所有结果：
2》刷一个蓝，这样红是偶数，蓝是奇数，一种刷法； 此时第二块只能刷蓝，一种刷法。
3》刷一块红，这样红是奇数，蓝是偶数，一种刷法； 此时第二块只能刷红，一种刷法。
（红，蓝） 结果， （偶， 偶），（奇， 偶）， （偶， 奇）
我们马上联想到还应有一个（奇， 奇）， 只是在只刷一块时这种可能性为0；

由此可得刷两块时结果为4+1+1 = 6；
但当刷三块时，结果又依赖于刷两块时的其它结果；
刷两块的所有可能结果为（偶，偶）（偶，奇）（奇，偶）（奇，奇）
由此我们来推断通用表达式：设a[i-1]为第i-1块刷完后结果为（偶，偶）的刷法，b[i-1]为（偶，奇）结果，同理c[i-1],d[i-1]
a[i] = 2a[i-1]+b[i-1]+c[i-1]+0d[i-1];
b[i] = a[i-1] + 2b[i-1] + 0c[i-1] + d[i-1];
c[i] = a[i-1] + 0b[i-1] + 2c[i-1] + d[i-1];
d[i] = 0a[i-1]+ b[i-1] + c[i-1] + 2d[i-1];
相信到这里大家都可以写出答案了，稍后时间整理代码和大家交流。

public class BrushWall {
	public static int base = 10007;
	public static int[][] Multi(int[][] a, int[][] b){
		int[][] result = new int[a.length][b[0].length];
		for(int i = 0; i < result.length; i++){
			for(int j = 0; j < result[0].length; j++){
				result[i][j] = 0;
			}
		}
		for(int i = 0; i < a.length; i++){
			for(int j = 0; j < b[0].length; j++){
				for(int k = 0; k < a[i].length; k++){
					result[i][j] += a[i][k]*b[k][j];
				}
				result[i][j] %= 10007;
			}
		}
		return result;
	}
	public static void printMatrix(int[][] data){
		for(int i = 0; i < data.length; i++){
			for(int j = 0; j < data[0].length; j++){
				System.out.print(data[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	public static void initMatrix(int[][] data){
		for(int i = 0; i < data.length; i++){
			for(int j = 0; j < data[0].length; j++){
				data[i][j] = 0;
				if(i == j){
					data[i][j] = 1;
				}
			}
		}
	}
	public static void matrixAdd(int[][] a, int[][] b){
		for(int i = 0; i < a.length; i++){
			for(int j = 0; j < a[0].length; j++){
				a[i][j] += b[i][j];
			}
		}
	}
	public static int[][] pow(int[][] a, int n){
		int[][] result = new int[a.length][a[0].length];
		initMatrix(result);
		while(n > 0){
			if((n & 1) != 0) result = Multi(result, a);
			a = Multi(a, a);
			n >>= 1;
		}
		return result;
	}
	public static void main(String[] args){
		int[][] matrix = new int[][]{{2, 1, 1, 0},{1, 2, 0, 1},{1, 0, 2, 1},{0, 1, 1, 2}};
		int number = 2;
		if(number == 1) {
			System.out.println("There have " + 2 + " way to brush the wall");
			return;
		}
		int[][] result = pow(matrix, 1);
		int methods = 2*result[0][0] + result[1][0] + result[2][0];
		System.out.println("There have " + methods + " way to brush the wall");
	}
}