[LeetCode] 62. Unique Paths - python
코드해설!Permalink
이번 문제는 초등학생때 한 번 쯤은 풀었던 모든 경우의 길 갯수 찾기 문제! 아주 간단해서 금방 풀어버렸습니다~
이동 방향이 아래, 오른쪽 밖에 되지 않고, 가장 오른쪽 아래의 도착지점까지의 모든 경우의 경로 갯수를 찾아야 하니, 아무런 조건없이 모든 경로의 갯수를 찾아주면된다!
따라서, 가장 첫번째 행과 열은 1로 초기화를 해주고, 나머지 빈칸들은 왼쪽에서 오른쪽, 위 아래로 차례로 돌면서 현 위치의 왼쪽과 위쪽 cost 를 더해줘가면 된다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution(object): | |
def uniquePaths(self, m, n): | |
""" | |
:type m: int | |
:type n: int | |
:rtype: int | |
""" | |
#grid = [[0] * n for i in range(m)] | |
cost = [[0] * n for i in range(m)] | |
for i in range(m): | |
cost[i][0] = 1 | |
for j in range(n): | |
cost[0][j] = 1 | |
for i in range(1, m): | |
for j in range(1, n): | |
cost[i][j] = cost[i-1][j] + cost[i][j-1] | |
return cost[m-1][n-1] | |
if __name__ == '__main__': | |
sol = Solution() | |
solution = sol.uniquePaths(m=3, n=2) | |
print(solution) |
댓글남기기