https://school.programmers.co.kr/learn/courses/30/lessons/12913?language=python3
두번째 DP 문제인데, 이전에 거스름돈 문제에 비하면 풀만했다.
아직 구현 능력이 부족하여 visualization을 거쳐, 코드를
수정했지만 스스로 사고하여 풀었단 점에서 의미가 있다.
핵심은 현재 행의 값을 갱신 시, 바로 이전 행의 값만 이용하는 것이다.
위의 샘플 케이스로 따지면,
우선 dp배열의 첫번째 행은 그대로 [1,2,3,5]로 둔다.
두번째 행 첫번째 열부터 첫번째 행의 서로 다른 열(두번째, 세번째, 네번째 열)들과 비교한다.
더 큰 값이 나오면 갱신시켜 준다.
그러면 dp[1] 즉 두번째행은 [10, 11, 12, 11]이 된다.
그렇게 구해진 두번째 행으로 세번째 행을 계산하면, dp[2] 는 [16, 15, 13, 13]이 된다.
최종적으로 최고점은 16이 된다.
코드는 아래와 같다.
...