백준 14494 다이나믹이 뭐에요?

백준 14494 다이나믹이 뭐에요?

해설

n*n의 2차원 공간에서 오른쪽, 아래쪽, 우아래 대각 세 방법만 이용하여 이동한다고 하자. 이때 임의의 점 (x, y)에 도달 할 수 있는 경우의 수 f(x, y)는 f(x-1,y) + f(x, y-1) + f(x-1, y-1)이다.

d배열을 1칸 크게 잡는다면 특별히 배열 range-exception 처리를 할 필요 없이 온전하게 연산에만 집중할 수 있다.

#include  
#define MOD ((int)1e9+7) 

using namespace std; 

int d[(int)1e3+1][(int)1e3+1]; 

int main() 
{ 

  int n, m; 
  cin >> n >> m; 

  d[0][0] = 1; 
  for (int i=1; i<=n; i++) 
  { 
    for (int j=1; j<=m; j++) 
    { 
      d[i][j] = d[i-1][j-1]; 
      d[i][j] += d[i][j-1]; 
      d[i][j] %= MOD; 

      d[i][j] += d[i-1][j]; 
      d[i][j] %= MOD; 
    } 
  } 

  cout << d[n][m]; 
}