[DP] 한 칸씩 이동하여 최대 합 구하기.

조건

1. 각 칸에 숫자가 적혀있는 판이 존재한다.
2. 이동은 (i+1, j), (i+1, j+1)만 가능하다.

풀이

1. 마지막 방문 위치가 dp[i][j]일 때, 해당 위치에 도달할 수 있는 경우는 바로 위에서 내려온 경우, 왼쪽 대각선 위에서 내려오는 경우 두가지 경로가 존재한다.
2. 이전 위치와 현재 위치의 값을 합한 후, 최대값을 dp[i][j]에 저장한다.

점화식

dp[i][j] = max(dp[i-1][j] + a[i][j], dp[i-1][j-1] + a[i][j])