With the automated teller machine (ATM) cash replenishment problem, banks aim to reduce the number of out-of-cash ATMs and duration of out-of-cash status. On the other hand, they want to reduce the cost of cash replenishment, as well. The problem conventionally involves forecasting ATM cash withdrawals, and then cash replenishment optimization based on the forecast. The authors assume that reliable forecasts are already obtained for the amount of cash needed in ATMs. The focus of the article is cash replenishment optimization. After introducing linear programming-based solutions, the authors propose a solution based on dynamic programming. Experiments conducted on real data reveal that the proposed approach can find the optimal solution more efficiently than linear programming.