아이디어 처음엔 삼각형의 위에서부터 1층, ..., k층, ..., n층으로 생각하고 k층까지의 최적의 경로가 n층까지의 최적의 경로에 포함될 것이라 생각할 수도 있다. 그러나 예시로 주어진 테스트케이스가 그 반례이다. 따라서 최적의 경로는, 2차원배열의 각 인덱스에 해당하는 dp[i][j]에 저장되어있다. 그러므로 dp[i][j]에 도달하는 optimal한 경로와 dp[i][j+1]에 도달하는 경로가 다를 것이다. dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + arr[i][j]; 를 사용하여 해결하면 된다. 다시 말하자면, k층까지 탐색했을 때 합이 최대가 되는 것이 최적의 경로가 아니라, k층의 l열을 오는 데에 합이 최대가 되는 경로가 최적의 경로(dp의 점화식)을 구..
