다이나믹 프로그래밍

다이나믹 프로그래밍

프로그래밍을 하며 다이나믹 프로그래밍에 쓰일 수 있는 사고방식을 모읍니다.

간단한 점화식(브론즈~실버3)

간단한 점화식 사고방식. DP[i] = DP[i-1] + DP[i-2] 와 같이 간단한 점화식으로 풀리는 문제들이 있다.

길이 여럿인 점화식(실버1)

RGB거리 1149번 다이나믹 프로그래밍에서 중요한 건 현재를 구성하는 방법이다. 현재 색이 R이면 이전 색은 B 혹은 G이다. 이것에서 방법을 착안하여, DP 배열을 3갈래로 만들면 현재 색이 R일 때의 최솟값, B일 때의(이하 생략)

        DP[i][0] = min(DP[i-1][1]+RGB[i][0], DP[i-1][2]+RGB[i][0]);
        DP[i][1] = min(DP[i-1][0]+RGB[i][1], DP[i-1][2]+RGB[i][1]);
        DP[i][2] = min(DP[i-1][1]+RGB[i][2], DP[i-1][0]+RGB[i][2]);