棋盘

题目描述：

请编写一个函数（允许增加子函数），计算n x m的棋盘格子（n为横向的格子数，m为竖向的格子数）沿着各自边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。

解题思路：
1、变成子问题：最左上角的可以看成点(n,m),最右下角看成(0,0);从点(n,m)向下走一步，后面就是子问题(n-1,m)的解；从点(n,m)向右走一步，后面就是子问题(n,m-1)的解.即F(n,m)=F(n−1,m)+F(n,m−1).$F(n,m)=F(n-1,m)+F(n,m-1).$
2、当n==0或者m==0时，只能有一种走法。
方法一、暴力搜索

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

方法二、动态规划

import java.util.Scanner;
public class Chessboard {
    public  int chessboard(int n,int m){
        if(n == 0 || m == 0){
            return 1;
        }
        int[][] count=new int[n + 1][m + 1];
        count[0][0] = 0;
        for(int i = 0;i <= n;i++){
            for(int j = 0;j <= m;j++){
                if(i == 0 || j == 0){
                    count[i][j] = 1;
                }else {
                    count[i][j] = count[i][j - 1] + count[i - 1][j];
                }
            }
        }

        return count[n][m];
    }
    public static void main(String[] args) {
        Chessboard cbd=new Chessboard();
        System.out.print(cbd.chessboard(3,4));
        /*Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            System.out.println(chessboard(n, m));
        }*/
    }

}

自顶向上：

public class Chessboard {
    public static int[][] count;
    public int solve(int n, int m){
        if(count[n][m]>=0){
            return count[n][m];
        }
        count[n][m] = solve(n-1,m) + solve(n,m-1);
        return count[n][m];
    }
    public int chessboard(int n, int m){
        if(n == 0 || m == 0)
            return 1;
        count = new int[n + 1][m + 1];
        for(int i = 0; i < count.length; i++){
            for(int j = 0; j < count[0].length; j++){
                if(i == 0 || j == 0){
                    count[i][j] = 1;
                }else{
                    count[i][j] = -1;
                }

            }

        }
        return solve(n,m);
    }    
}