leetcode 62. Unique Paths 逃离我推掉我的手 2022-08-21 04:13 102阅读 0赞 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? ![robot_maze.png][] Above is a 3 x 7 grid. How many possible unique paths are there? Note: m and n will be at most 100. class Solution { public: int uniquePaths(int m, int n) { if (m == 1 || n == 1) return 1; //return uniquePaths(m - 1, n) + uniquePaths(m, n - 1); if (m > n) { int t = n; n = m; m = t; } long long int numer = 1; long long int denomi = 1; for (int i = m + n - 2; i >= n; i--) numer *= i; for (int i = 1; i <= m - 1; i++) denomi *= i; return numer / denomi; } }; 简单考虑一下,就是一个排列组合问题,直接写公式就行(递归显然效率不高)。 accepted [robot_maze.png]: http://leetcode.com/wp-content/uploads/2014/12/robot_maze.png
还没有评论,来说两句吧...