- 다시 풀어야 함.
점화식
-> 그런데 여기서 진행하려고 하면, 모두 0으로 설정됨.
뭔가 더 해야할 듯함.
- 점화식을 생각해보면 일단. 이차원배열임.
d[i][j] 라고 명시했을 때
d[i][0], d[i][1] , d[i][2]
: i번열에서 빨강을 선택했을 때는 앞단에서는 파랑과 초록을 선택해야 함.
이런식으로 정의할 수 있음.
d[i][0] = min(d[i - 1][1] , d[i - 1][2]) + v[i][0];
//
쉽게 접근을 해야함!
현재 인덱스가 나타내는 것은 빨 파 초 임.
빨 파 초
26 40 83
49 60 57
13 89 99
여기에서 빨 49를 선택했다면? 49번 입장에서 봤을 때는
윗단에서 26을 제외하고, min(40과 83)을 선택해야만 했음!
여기에서 파 60를 선택했다면? 60번 입장에서 봤을 때는
윗단에서 40을 제외하고, min(26과 83)을 선택해야만 했음!
~ 이런식으로 마지막 인덱스 까지 누적을 해서
n단 원소에서 최소값을 추출하면 될듯 함.
🔥🔥🔥