계단마다 비용이 있고 한 칸 또는 두 칸씩 올라 꼭대기에 도달하는 최소 비용을 구하는 문제다. 밟은 칸의 비용을 낸다.
stairs = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
100이 박힌 자리를 피해 가는 게 관건이다.
경로를 다 만들어보기
def rec(cur, sum=0):
if len(cur) <= 1:
store.append(sum)
return
rec(cur[1:], sum + cur[0])
rec(cur[2:], sum + cur[1])
store = []
rec(stairs)
print(min(store))
리스트를 잘라가며 내려간다. 한 칸 오르면 cur[0] 을 내고 cur[1:] 이 남고, 두 칸이면 cur[1] 을 내고 cur[2:] 가 남는다.
답은 6이고 만들어진 경로는 89개다. 계단 10개에 89개니 계단이 늘어나면 피보나치 수만큼 불어난다.
남은 길이만 상태로
cur 를 통째로 들고 다니는데, 실제로 다른 건 남은 길이 하나다. 길이가 같으면 앞으로 낼 비용도 같다.
def dyna(cur_len):
if cur_len in dp:
return dp[cur_len]
dp[cur_len] = min(dyna(cur_len - 1), dyna(cur_len - 2)) + stairs[cur_len]
return dp[cur_len]
length = len(stairs)
stairs.append(0)
dp = {-2:0, -1:0}
dyna(length)
print(dp[length])
리스트를 자르지도 않는다. 인덱스 하나만 넘긴다.
경계를 없앤 두 가지 장치
이 코드에서 가장 마음에 드는 부분이다. 보통 if cur_len < 0: return 0 같은 걸 넣는데 여기엔 없다.
stairs.append(0)
비용 0짜리 계단을 끝에 하나 붙였다. 꼭대기가 실제 계단이 되므로 "다 올라왔다"를 따로 처리할 필요가 없다. dyna(length) 가 그 가상의 계단이다.
dp = {-2:0, -1:0}
음수 인덱스를 미리 채워뒀다. dyna(0) 은 dyna(-1) 과 dyna(-2) 를 부르는데, 둘 다 dp 에 이미 있어서 바로 0을 돌려준다. 재귀가 거기서 멈춘다.
두 개 다 종료 조건을 코드가 아니라 데이터로 옮긴 것이다. if 가 하나도 없이 세 줄로 끝난다.
아래에서 위로도 써봤다
dp = {-2:0, -1:0}
for i in range(length):
dp[i] = min(dp[i - 1], dp[i - 2]) + stairs[i]
같은 점화식을 반복문으로 돌린 것이다. dict를 그대로 써서 dp[-1] 과 dp[-2] 가 초기값으로 잡히는 것도 같다.
다만 range(length) 라 i 가 9까지만 간다. 끝에 붙여둔 비용 0짜리 계단인 dp[10] 은 계산되지 않는다. 이 입력에서는 dp[9] 가 6이라 답이 맞아 보이는데, 마지막 계단이 비쌌다면 그 칸을 건너뛰는 선택을 못 하게 된다. range(length + 1) 이어야 위쪽 재귀 버전과 같아진다.