동적프로그래밍 길찾기 [C 언어]

#include 

#define M 100
#define N 100

int map[M][N];

long long num_path(int m, int n)
{
  // 장애물이면 0
  if (map[m][n] == 0) {
    return 0;
  }
  // m=i,n=j에서 0,0으로 갔으면 +1
  if (m == 0 && n == 0) {
    return 1;
  }
  
  return ((m > 0) ? num_path(m - 1, n) : 0)
    + ((n > 0) ? num_path(m, n - 1) : 0);
}

// 와... 값을 리턴하는 것이 아닌 map에 값을 넣는다.
long long path[M][N];
void dynamic_programming_path(int m, int n)
{
  int i, j;  // 이중포문용
  path[0][0] = map[0][0];
  
  
  // 1. 세로 맨 왼쪽은 왼쪽을 더할필요가 없음.
  for(i = 1; i < m; ++i) { //i=0 : path[-1][0]이 없기 때문에 스킵
    if (map[i][0] == 0) {
      path[i][0] = 0;
    } else {
      path[i][0] = path[i-1][0];  // 2. 여기 path[i][0-1]
    }
  }
  // 2. 가로 맨 왼쪽은 위쪽을 더할 필요가 없음.
  for(j = 1; j < n; ++j) { // j=0 은 path[0][-1]가 없기 때문에 스킵
    if (map[0][j] == 0) {
      path[0][j] = 0;
    } else {
      path[0][j] = path[0][j-1]; // 2. 여기 path[0-1][j]
    }
  }

  for (i = 1; i < m; i++) {
    for (j = 1; j < n; j++) {
      if (map[i][j] == 0) {
        path[i][j] = 0;
      } else {
        // 동적프로그래밍 한칸 한칸 나아간다.
        path[i][j] = path[i-1][j] + path[i][j-1];
      }
    }
  }
}


/*
5 5
1 1 1 1 1
1 1 0 0 1
1 1 1 1 1
1 1 1 0 1
0 0 1 1 1
*/
int main(void) {
  int m, n, i, j;

  scanf("%d %d", &m, &n);
  for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++) {
      scanf("%d", &map[i][j]);
    }
  }
  // 반대로 가는듯.
  // printf("%lld\n", num_path(m-1, n-1));
  dynamic_programming_path(m, n);

  return 0;
}

출처: 문제로 풀어보는 알고리즘