[LeetCode 63] Unique pathII 동적 기획 문제 풀이 예시

제목 설명
격자 하 나 를 지정 합 니 다. 격자 에 있 는 모든 격자 는 0 과 1 로 표시 합 니 다. 그 중에서 0 은 이 격자 가 통과 할 수 있 음 을 나타 내 고 1 은 이 격자 에 장애물 이 있어 통과 할 수 없다 는 것 을 나타 냅 니 다.따라서 이 격자 는 n * m 의 행렬 M 으로 표시 할 수 있 는데 그 중에서 행렬 요 소 는 1 과 0 만 포함 하고 M [0] 에서 M [n - 1] [m - 1] 까지 몇 가지 서로 다른 경로 로 도착 할 수 있 으 며 매번 이동 할 때마다 아래로 또는 오른쪽으로 만 이동 할 수 있다.예 를 들 어 주어진 격자 가 아래 의 격자 행렬 이다.
4. 567913. 수출 결 과 는 2 로 [0] [0] 에서 [2] [2] [2] 까지 아래로 이동 하고 오른쪽으로 이동 하 는 두 가지 서로 다른 경로 로 도착 할 수 있 음 을 나타 낸다.
2. 사고방식 해석
이 문 제 는 주로 동태 계획 의 사상 을 사용 하 는데 동태 계획 의 핵심 사상 은 지난 단계 에 얻 은 수출 결 과 를 다음 단계 에 계산 하 는 입력 으로 하 는 것 이다.이 문제 에서 우 리 는 [0] [0] 에서 [n - 1] [m - 1] 까지 모두 몇 가지 경로 가 있 는 지 계산 해 야 한다. f (M [n - 1] [m - 1]) 로 이동 할 때 아래로 이동 하거나 오른쪽으로 이동 할 수 밖 에 없 기 때문에 [n - 1] [m - 1] 이전에 도착 한 격자 는 [n - 2] [m - 1] 또는 [n - 1] [m - 2] 에서 두 개 만 얻 을 수 있 기 때문에 f (M [n - 1] [m - 1]) 를 쉽게 얻 을 수 있다. = f(M[n-2][m-1]) + f(M[n-1][m-2])。그러면 우 리 는 다음 에 f (n - 2) 와 f (n - 1) 의 값 만 계산 하면 된다.마찬가지 로 f (M [n - 2] [m - 1]) 또는 f (M [n - 1] [m - 2]) 에 대해 서도 항소 방향 으로 계산 할 수 있다.마지막 으로 모든 M [i] [j] 에 대해 우 리 는 f (M [i] [j]) 를 얻 을 수 있 고 행렬 M 과 같은 크기 의 행렬 F 를 얻 을 수 있 으 며 F [n - 1] [m - 1] 을 출력 하면 된다.
행렬 F 를 계산 하 는 방법 은 사실 매우 간단 하 다. 먼저 F [0] [j] 와 F [i] [0] 의 값, 즉 행렬 의 첫 줄 과 첫 번 째 열 을 계산한다.첫 줄 과 첫 번 째 열 에 대해 어떤 M 값 이 1 이면 이전의 F 값 은 모두 1 이 고 그 다음 에는 모두 0 이다.그 다음 에 각 칸 의 f [i] [j] 에 대해 f [i] [j] = f [i - 1] [j] + f [i] [j - 1] 이 있 고 M 값 이 1 이면 대응 하 는 F 값 은 0 이 며 순서대로 유추 하여 행렬 F 를 얻 을 때 까지 F [n - 1] [m - 1] 을 출력 하면 된다.행렬 M 의 경계 상황 을 주의 하면 됩 니 다.
3. 코드 구현

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]