[질문] 종만북 214쪽 질문

[익명(121.174)]

bino2(n, r)을 계산할 때 만날 수 있는 부분 문제의 수가 최대 O(n^2) 라고 하는데, 이게 왜 n^2인지 좀 설명해줄수 있음?

잘 이해가 안가네... 예를 들어, n이 3 이라고 하면, bino2(3, 1), bino2(3, 2), bino2(3, 3) 각각 호출할때 뻗어나오는 재귀함수 개수인거임?

[-_-(71.251)]

bino2()를 계산해야 하는 입력의 개수인거임. 메모이제이션 안하면 같은 입력에 대해 bino2()를 여러번 계산해야 하니 호출회수는 그거보다 훨씬 많을 수 있지