오버플로
문제를 푸는 과정, 또는 정답에서 경우의 수를 구해야 하는 경우 구하고자 하는 정수의 수가 너무 커져서 int형의 size 4바이트를 초과해서 오버헤드가 발생할 수 있다. 이 경우 재귀 함수의 반환값에 모듈로 연산을 처리해 주면, 수의 크기가 훨씬 줄어들어 오버헤드를 방지할 수 있다.
예제 - 삼각형 위의 최대 경로 수
이 전에 풀었던 삼각형 위의 최대 경로 구하기 문제에서 경로의 수를 구하는 문제로 문제를 약간 변형했다. 경우의 수를 구하기 위해서는 먼저 최적화 문제를 풀어 문제의 배열을 경우의 수를 구하기 알맞게 바꿔준 뒤, 또 다른 동적 계획법을 설계해서 문제를 해결한다.
배열을 수정해 주는 이유는 경우의 수를 구하기 위한 배열을 만들기 위해서 부분 문제로 나뉘는 포인트마다 이 전에서 구한 값에 상관 없이 새로운 부분 문제를 만들 수 있게 하기 위함이다. 부분 문제로 나뉘는 부분은 배열의 값에 따라 조건문을 이용해 알맞게 나뉠 수 있도록한다.
확률
단순 경우의 수가 아닌 확률이 포함된 문제 역시 그 과정은 크게 다르지 않다. 문제가 요구하는 경우의 수를 전체 경우의 수로 나눠주면 그 확률을 구할 수 있다. 또는 재귀 함수가 직접 확률을 반환하게 할 수도 있다.
예제 - 우물 달팽이
우물을 기어오르는 달팽이가 50퍼센트의 확률로 비가 오면 2m, 오지 않으면 1m 우물 위로 이동하는데, 주어진 날 안에 우물을 다 기어오를 확률을 구하는 문제이다.
먼저 완전 탐색을 통해 접근한다. 지금까지 달팽이가 사용한 날의 수와 오른 길이를 파라미터로 한 재귀 함수를 만든다.
매 부분 문제는 달팽이가 지금까지 사용한 날과 올라온 길이를 목표로 하는 날과 길이에서 뺀 값에 대한 부분 문제인 것이다.
만약 비가 올 확률이 75퍼센트가 된다면 어떻게 될까, 이 경우 매번 경우의 수를 구해서 그 합을 반환하는 것이 아니라, 점화식의 계수에 확률을 포함시켜 확률을 반환하게 하게끔 한다.
