本文主要是介绍《leetCode》：Unique Paths，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).How many possible unique paths are there?
Note: m and n will be at most 100.
思路一
思路：用递归来求解即可
一个点的路径总数等于右边节点的路径总数+正下方节点的路径总数
实现代码如下：
int uniquePaths(int m, int n) {if(m==1&&n==1){return 0;}if(m==1||n==1){return 1;}return uniquePaths(m,n-1)+uniquePaths(m-1,n);
}报超时错误，截图如下：
我在自己电脑的编译环境试了下，虽然在我的电脑上能够得到正确结果，但是我观察了下确实运行的时间过长。
测试代码如下：
int main(void){int m,n;while(scanf("%d%d",&m,&n)!=EOF){int result=uniquePaths(m,n);printf("%d \n",result);}return 0;
}
出现这样的原因在于：递归深度过大。因此我们需要寻找更好的方法。
思路二：用空间来换取时间
借助空间来换取时间；
开辟一个m*n的数组空间，用来存储每个点到终点的可达路径的总数；
计算方法为：一个点的路径总数等于右边节点的路径总数+正下方节点的路径总数
int uniquePaths(int m, int n) {if(m<1||n<1){return 0;}if(m==1||n==1){return 1;}//开辟一段空间来保存结果int **result=(int **)malloc(m*sizeof(int *));if(result==NULL){exit(EXIT_FAILURE);}for(int i=0;i<m;i++){result[i]=(int *)malloc(n*sizeof(int));if(result[i]==NULL){exit(EXIT_FAILURE);}}result[m-1][n-1]=0;//最后一列为 1；for(int i=0;i<m;i++){result[i][n-1]=1;}//最后一行为 1；for(int i=0;i<n;i++){result[m-1][i]=1;}for(int i=m-2;i>=0;i--){for(int j=n-2;j>=0;j--){result[i][j]=result[i+1][j]+result[i][j+1];}}return result[0][0];
}最后AC结果如下：
这篇关于《leetCode》：Unique Paths的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
