有一个m*n的矩阵,计算从其中一个顶点出发,以对角的顶点为终点,计算总共有多少种走法(每次只能走1个单位,不能往回走,假设从左上方顶点出发,每次只能向下或者向右走一个单位)

周明岐 发布于 2013/08/26 19:08
阅读 2K+
收藏 0
有一个 m*n 的矩阵,计算从其中一个顶点出发,以对角的顶点为终点,计算总共有多少种走法(每次只能走 1 个单位,不能往回走,假设从左上方顶点出发,每次只能向下或者向右走一个单位)
加载中
0
魔神翼
魔神翼
import java.math.BigInteger;
public class Main
{
    public static void main(String[] args)
    {
        int m = 100;
        int n = 100;
        BigInteger dp[][] = new BigInteger[m+1][n+1];
        for(int i = 0; i <= m; ++i)
        {
            for(int j = 0; j <= n; ++j)
            {
                dp[i][j] = BigInteger.ZERO;
            }
        }
        dp[1][1] = BigInteger.ONE;
        for(int i = 1; i <= m; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                if(dp[i][j].equals(BigInteger.ZERO))
                    dp[i][j] = dp[i-1][j].add(dp[i][j-1]);
            }
        }
        System.out.println(dp[m][n]);
        //System.out.println(dfs(dp, m, n));
    }
    
    public static int dfs(int dp[][], int x, int y)
    {
        if(x == 0 || y == 0 || dp[x][y] > 0)
            return dp[x][y];
        return dp[x][y] = dfs(dp, x-1, y) + dfs(dp, x, y-1);
    }
}

http://ideone.com/rdEArw

http://ideone.com/6sEYVQ

1
高得顺
高得顺

(M-1+N-1)!/((M-1)!*(N-1)!)

采纳个最佳答案吧

0
z
zjwzcnjsy
这个有规律吧!
0
z
zjwzcnjsy

f(m,n)=f(m-1,n)+f(m,n-1)

f(2,1)=1

f(1,2)=1

好像这样的?

周明岐
周明岐
如果用程序来表示呢
返回顶部
顶部