查找矩阵中唯一路径的数量

Question

给定一个初始位置在左上角单元格的 M X N 矩阵，找到从初始位置到达矩阵右下角单元格的可能唯一路径的数量。
可能的移动可以在任何时间点向下或向右移动。

对于 M=5，N=11 的输入。正确的输出应为 1001。
对于不同的 IDE，输出是不同的。

 #include<stdio.h>
 int div(int tot,int j,int n,int m)
 {
      int i;
      int fn=1;
      int fd=1;
      int f=1;
      int p;
      for(i=tot;i>=j;i--)
      {
              fn=fn*i;
      }
      for(i=n;i>=1;i--)
      {
              fd=fd*i;
      }
      p=fn/fd;
      for(i=j-1;i>=m+1;i--)
              f=f*i;
              p=p*f;
              return p;

}

int main()
{
              int M,N;
              int unqPath;
              int i,T;
              int j,path;
              int m,n;
              int flag=0;
              scanf("%d",&T);
              for(i=0;i<T;i++)
              {
                      scanf("%d",&M);
                      scanf("%d",&N);
                      if(M>=N)
    {
        path=1;
        for(j=(M-1)+(N-1);j>(M-1);j--)
        {
            path=path*j;
            if(path<=0)
            {
                unqPath=div(((M-1)+(N-1)),j+1,N-1,M-1);
                flag=1;
                printf("nn%d",unqPath);
                break;
            }
        }

        if(flag==0)
        {
            n=1;
            for(j=(N-1);j>=1;j--)
            {

                n=n*j;
            }
            unqPath=path/n;
            printf("%d",unqPath);
        }
    }
    else
    {
        path=1;
        for(j=(M-1)+(N-1);j>(N-1);j--)
        {

            path=path*j;
            if(path<=0)
            {
                unqPath=div((M-1)+(N-1),j+1,M-1,N-1);
                flag=1;
                printf("%d",unqPath);
                break;
            }
        }
        if(flag==0)
        {

            m=1;
            for(j=(M-1);j>=1;j--)
            {
                m=m*j;
            }
            unqPath=path/m;
            printf("n%d",unqPath);
        }
    }
}
    return 0;
}

Answer 1

你的程序太复杂了。您应该首先研究构建路径以赢得时间的方式。

在给定的点 x，y 处，您可以向下或向右移动。因此，从这一点开始的路径数是向下或向右移动时路径数的总和。
特殊情况是当点位于边界上时，其中只有一条路径。

因此，您将获得以下代码，其中包含计算的递归实现：

#include <stdio.h>
// cells are numbered (1..xmax, 1..ymax)
// x an y are position of points
// xmax and ymax are the rectangle size
int nbrpaths(int x, int y, int xmax, int ymax)
{
  if(x==xmax || y==ymax) return 1; // On a south or east border ->
                                   // only one solution: go straight right or down
  return nbrpaths(x+1,y,xmax,ymax)   // go right and find a path 
        + nbrpaths(x,y+1,xmax,ymax); // go down and find a path
}
int main()
{
  int xmax=5, ymax=11, x=1, y=1;
  int nbr=nbrpaths(x,y,xmax,ymax);
  printf("number of paths: %dn",nbr);
}
// prints: number of paths: 1001

Answer 2

如果矩阵为 n x m，则唯一路径的数量为 (n+m-2(！/((n-1(！(m-1(！您可以简单地编写该公式。

请参阅维基百科中的组合。

Answer 3

你可以

这样看：

当您位于左上角并向下移动时，您将获得一个新矩阵，其中少了 1 行和相同数量的列。

当您位于左上角并移动 1 个 rigth 然后向下移动时，您将获得一个新矩阵，其中少了 1 行和 1 列。

当您在左上角并移动 2 个 rigth 然后向下移动时，您会得到一个新矩阵，其中少了 1 行和 2 列。

等等。

因此，要计算 (R， C( 矩阵的结果，您可以将其计算为来自多个较小矩阵的结果之和。喜欢：

count(R, C) = count(R-1, C-0) + count(R-1, C-1) + count(R-1, C-2) + ... + count(R-1, 1)

这可以通过递归来处理。像这样：

#include <stdio.h>
int count(int r, int c)
{
  if (r == 1) return 1;
  if (c == 1) return 1;
  int sum = 0;
  for (int i=0; i < c; ++i)
  {
      sum += count(r-1, c-i);
  }
  return sum;
}
int main()
{
  int r=5, c=11;
  int res=count(r,c);
  printf("Result: %dn", res);
}