2차원 배열의 합

https://www.acmicpc.net/problem/2167

풀이

• dp

• 그림으로 쉽게 풀림

• 점화식
  ​

    s[i][j] = a[i][j] + s[i-1][j] +s[i][j-1] - s[i-1][j-1] 
  

• ( i,j,x,y 의 구간합 )

    s[x][y] -s[ i-1][y]  - s[x][j-1] + s[i-1][j-1 ]