动态规划问题 - 小兵向前冲

题目描述：

N*M的棋盘，小兵从左下角走到右上角，只能向上或向右走，问有多少种走法？

解答：

解法一：

	public static int trace(int m, int n) {
		if(n < 1 || m < 1)
			return 0;
		if(n == 1 && m == 1)
			return 1;
		return trace(m - 1, n) + trace(m, n - 1);
	}

时间复杂度：2^(n + m)

解法二：

	public static int trace(int m, int n) {
		int[][] num = new int[m + 1][n + 1];
		if(n < 1 || m < 1) {
			return 0;
		}
		if(n == 1 && m == 1) {
			num[1][1] = 1;
			return num[1][1];
		}
		if(num[m][n] > 0) {
			return num[m][n];
		}
		else {
			num[m][n] = trace(m - 1, n) + trace(m, n - 1);;
			return num[m][n];
		}
	}

时间复杂度：m*n

问题扩展：

1. 如果某些格子禁止小兵进入，怎么处理？

	public static int trace(int m, int n, int m0, int n0) {
		int[][] num = new int[m + 1][n + 1];
		if(n < 1 || m < 1) {
			return 0;
		}
		if(n == 1 && m == 1) {
			num[1][1] = 1;
			return num[1][1];
		}
                if(n == n0 && m == m0){
                        num[m][n] = 0;
                        return num[m][n];
                }                
		if(num[m][n] > 0) {
			return num[m][n];
		}
                
		else {
			num[m][n] = trace(m - 1, n) + trace(m, n - 1);;
			return num[m][n];
		}
	}

2. 如果小兵在一个方向上可以走一步或两步？

	//假设在m方向上可以走一步或两步
        public static int trace(int m, int n) {
		int[][] num = new int[m + 1][n + 1];
		if(n < 1 || m < 1) {
			return 0;
		}
		if(n == 1 && m == 1) {
			num[1][1] = 1;
			return num[1][1];
		}
		if(num[m][n] > 0) {
			return num[m][n];
		}
		else if(m <= 2)
                {
			num[m][n] = trace(m - 1, n) + trace(m, n - 1);
			return num[m][n];
		}
                else{
                        num[m][n] = trace(m - 1, n) + trace(m, n - 1) + trace(m - 2,n);
                        return num[m][n];
                }    
	}