aux(n, k) : k 번째 수를 포함하는 합이 최대값이 되는 경로의 합

aux(n,k ) = max(aux(n-1, k-1), aux(n-1, k)) + value[n, k]

f(n) : max(aux(n, 0)...aux(n-1))

구현해보니 정답이 되네요.

n이랑 k가 1인 경우는 aux(0,0) aux(0,1)중에서 고르게되는 데 aux(0,1)은 안나오지 않나요...?? 

aux(0,1)은 -1이라서 상관없나요? 

범위 밖을 참조할때는 0을 반환하게끔 해주었습니다.

재귀함수의 base case가 0인 셈이겠네요.

1

1

과 같이 말씀하신 경우라면 max(0, 0) + 1 이 되겠습니다.

감사합니다! 설명 잘들었습니다.