Problem:
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?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
Idea:
Dynamic Programming
Solution1:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: int uniquePaths(int m, int n) { if (m < 0 || n < 0) return 0; if (m == 1 && n == 1) return 1; if (f_[m][n] > 0) return f_[m][n]; int left_paths = uniquePaths(m - 1, n); int top_paths = uniquePaths(m, n - 1); f_[m][n] = left_paths + top_paths; return f_[m][n]; } private: unordered_map<int, unordered_map<int, int>> f_; }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua // Running time: 0 ms class Solution { private int[][] dp; private int m; private int n; public int uniquePaths(int m, int n) { this.dp = new int[m][n]; this.m = m; this.n = n; return dfs(0, 0); } private int dfs(int x, int y) { if (x > m - 1 || y > n - 1) return 0; if (x == m - 1 && y == n - 1) return 1; if (dp[x][y] == 0) dp[x][y] = dfs(x + 1, y) + dfs(x , y + 1); return dp[x][y]; } } |
Solution2:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: int uniquePaths(int m, int n) { auto f = vector<vector<int>>(n + 1, vector<int>(m + 1, 0)); f[1][1] = 1; for (int y = 1; y <= n; ++y) for(int x = 1; x <= m; ++x) { if (x == 1 && y == 1) { continue; } else { f[y][x] = f[y-1][x] + f[y][x-1]; } } return f[n][m]; } }; |