동적 계획법을 이용하지 않으면 똑같은 f(a, b)가 호출될 때마다 f(a-1, b) + f(a, b-1)을 다시 호출한다는 이야기고, 그것들 각각은 또 2개씩의 함수를 호출할 것이며, 그 각각이 또 2개씩을 호출하고... 가 연쇄적으로 일어날 뿐만 아니라 각 호출이 수없이 많이 중복해서 일어날 수도 있게 됩니다.
반면 동적 계획법을 이용하면 모든 a, b 쌍에 대해 f(a, b)는 딱 한 번만 연산을 하면 되고 그 이후로는 이전에 구해둔 값을 그대로 사용하기만 하면 되므로 a, b의 쌍의 수만큼만 연산이 필요합니다.
ekdns7952 5년 전