There is a robot on an m x n
grid. The robot is initially located at the top-left corner (i.e., grid[0][0]
). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]
). The robot can only move either down or right at any point in time.
Given the two integers m
and n
, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * .
Input : m = 3, n = 7
Output : 28
Input : m = 3, n = 2
Output : 3
Explanation : From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
1 <= m, n <= 100
๋ฌธ์ ์ ์ ์๋ ์์๋ฅผ ๊ธฐ์ค์ผ๋ก ๊ฒฝ์ฐ์ ์๋ฅผ ๊ตฌํ๋ค ๋ณด๋ฉด์ ํ ๊ฐ์ง ๊ท์น์ ๋ฐ๊ฒฌํ ์ ์์๋ค.
์ด์ ๊ฒฝ๋ก๋ค์ ์ต๋จ ๊ฒฝ๋ก ๊ฒฝ์ฐ์ ์์ ํฉ์ด ํ์ฌ ๊ฒฝ๋ก์ ์ต๋จ ๊ฒฝ๋ก๊ฐ ๋๋ค๋ ๊ฒ์ด๋ค.
์ด๋ฅผ ์ ํ์์ผ๋ก ํํํ๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
grid[m][n] = grid[m-1][n] + grid[m][n-1]
์ด์ ์ด ์ ํ์์ ์ฝ๋๋ก ์ฎ๊ฒจ ์ฃผ๊ธฐ๋ง ํ๋ฉด ๋๋ค.
๊ทธ๋ฆฌ๋ ์ ์ฒด๋ฅผ ์ฐ์ 1๋ก ์ฑ์์ค๋ค.
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
grid[i][j] = 1;
}
}
๊ตฌํด๋์ ์ ํ์์ ๊ทธ๋๋ก ์ ์ฉ์ํค๊ธฐ๋ง ํ๋ฉด ๋ฌธ์ ๋ฅผ ๊ฐ๋จํ ํด๊ฒฐํ ์ ์๋ค.
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
grid[i][j] = grid[i-1][j] + grid[i][j-1];
}
}
public static int uniquePaths(int m, int n) {
int[][] grid = new int[m][n];
// ๊ทธ๋ฆฌ๋ ์ด๊ธฐํ
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
grid[i][j] = 1;
}
}
// ์ ํ์ ์ ์ฉ
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
grid[i][j] = grid[i-1][j] + grid[i][j-1];
}
}
return grid[m-1][n-1];
}
์์ ์ ๋ํ ๋?์์ ํ๋ ๋ฌธ์ ์๊ฐ๋๋น