알고리즘/알고리즘 문제 복기
LeetCode - 62. Unique Path
내일도무사히
2021. 4. 2. 08:31
leetcode.com/problems/unique-paths/
Unique Paths - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
Answer1. 재귀
맨처음에는 재귀를 이용해서 풀어봤다.
m이 가로의 길이고 n이 세로의 길이라 할 때
f(m, n) = f(m-1, n) + f(m, n-1)이라고 수식을 세웠다
그래서 위와같이 코드를 짰는데 시간 초과가 나서 다이나믹 프로그래밍으로 풀었다
Answer2 DP
위와같이 풀었는데 풀긴 했지만
여전히 속도가 그리 빠르지 않아 다른 방법도 찾아봐야겠다