명이나물 라이브러리

프로그래머스 등굣길, DP로 풀기이번에는 프로그래머스의 등굣길 문제를 풀어보았다.👉프로그래머스 등굣길 문제문제 설명집에서 학교까지 가는 길이 격자 형태로 주어진다.집은 왼쪽 위에 있고, 학교는 오른쪽 아래에 있다.이동은 오른쪽과 아래쪽으로만 할 수 있다.중간에 물웅덩이가 있는 칸은 지나갈 수 없다.이때 집에서 학교까지 갈 수 있는 최단 경로의 개수를 구해야 한다.단, 경로의 수가 매우 커질 수 있으므로 정답은 1,000,000,007로 나눈 나머지를 반환해야 한다.문제 유형 분류이 문제는 DP, 동적 계획법 문제이다.처음에는 DFS로 모든 경로를 탐색하면 되지 않을까 생각했다.각 칸에서 이동할 수 있는 방향은 최대 두 가지이다.오른쪽으로 이동아래쪽으로 이동그렇기 때문에 DFS로 모든 경로를 탐색할 수도..