在如下8*6的矩阵中,请计算从A移动到B一共有____种走法。要求每次只能向上或向右移动一格,并且不能经过P。

在如下8*6的矩阵中,请计算从A移动到B一共有____种走法。要求每次只能向上或向右移动一格,并且不能经过P。

解析:
8*6的矩阵,从左下角A到右上角B,一共需要走12步,其中5步向上,7步向右,因此总的走法一共有C(12,5)=792种,但题目规定不能经过P,因此需要减去经过P点的走法。
经过P的路径分为两部分,从A到P,从P到B。
同理,从A到P的走法:C(6,2)=15;
同理,从P到B的走法:C(6,3)=20;
因此从A到B经过P点的走法有15*20=300种,
所以从A到B不经过P点的走法有792-300=492种。

这题其实可以用程序算出来:
简单的动态规划:
dp[i][j] = dp[i][j-1] + dp[i-1][j];

程序:
public class Test {
    
    public static void main(String[] args) {
        int m = 8;
        int n = 6;
        int[][] dp = new int[m+1][n+1];
        dp[0][1] = 1;// 初始化
        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        
        // dp[4][4]代表P-B的步数,dp[3][5]代表A-P的步数
        System.out.println(dp[m][n] - dp[4][4] * dp[3][5]);
    }    
}

 

上一篇:Java job interview:项目架构研发58赶集通用的实时统计分析平台设计与实践


下一篇:快速排序*^____^*