首页 > 代码库 > leetcode第一刷_Unique Paths
leetcode第一刷_Unique Paths
从左上到右下,只能向右或向下,问一共有多少种走法。
这个问题当然可以用递归和dp来做,递归的问题是很可能会超时,dp的问题是需要额外空间。
其实没有其他限制条件的话,这个问题有个很简单的解法。给定一个格子,假设是m*n的,从左上角走到右下角的总步数是确定了的,(m+n-2)嘛,即在竖直方向一定要走m-1步,在水平方向一定要走n-1步。那有多少种解法就相当于确定什么时候往下走,什么时候往右走,也即相当于从这m+n-2步中,挑选出m-1步有多少种挑法,因为剩下的肯定要往右走嘛。问题实际上就是求c(m+n-2 , m-1),当然也等于c(m+n-2,n-1),具体用哪一个可以挑个小的好算的。
int getNum(int sum, int part){ if(part==0||part==sum) return 1; long long mpart = 1; for(int i=2;i<=part;i++) mpart *= i; long long msum = 1; for(int i=sum-part+1;i<=sum;i++) msum *= i; return (int)(msum/mpart); } class Solution { public: int uniquePaths(int m, int n) { return getNum(m+n-2, min(m-1, n-1)); } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。