접근
제약조건이 1 <= m, n <= 100 생각보다 크다. 완전탐색으로 하기에는 시간복잡도가 크다. 따라서 DP 방식으로 해결할 수 있는 방법을 생각해야 한다. 시작점의 행과 열은 한가지의 길 밖에 없으므로, 방법이 1가지이다. 따라서 시작점의 행과 열을 1로 초기화를 해주고, 이전 행과 열이 존재한다면 둘의 값을 합해주고 메모이제이션을 해준다.
Python
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[-1]*n for _ in range(m)]
dp[0][0] = 1
for i in range(n):
dp[0][i] = 1
for j in range(m):
dp[j][0] = 1
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i][j-1] + dp[i-1][j]
return dp[m-1][n-1]
print(f"==>> uniquePaths: {Solution().uniquePaths(3, 7)}")
Python
복사
TypeScript
function uniquePaths(m: number, n: number): number {
const dp = Array(m)
.fill(0)
.map((x) => Array(n).fill(1));
for (let i = 1; i < dp.length; i += 1) {
for (let j = 1; j < dp[0].length; j += 1) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
console.log('🚀 ~ uniquePaths ~ uniquePaths:', uniquePaths(3, 7)); //28
TypeScript
복사