Подскажите, пожалуйста, как тут посчитать правильно:
Один любитель азартных игр постоянно проигрывал в игровых автоматах. Он попросил своего приятеля-программиста разработать ему программу для КПК, которая помогла бы ему в оценке шансов в играх.
Входными данными должны быть два числа: N – максимальное число ходов в игре и М – число равновероятных исходов при одном ходе. (Например, при М = 6 получаем игру с кубиком, при М = 13 – с волчком как в игре «Что? Где? Когда?» и т.д.). Все исходы занумерованы от 1 до M. После любого хода (вплоть до N, когда игра сама закончится) игрок может остановиться, и результатом игры в этом случае** будет номер последнего исхода**. Нужно определить математическое ожидание результата игры при оптимальной стратегии играющего, то есть стратегии, которая максимизирует это математическое ожидание.
(N, M <= 100)
UPD: задача с West Siberian Subregional Contest 2011
Если я не ошибаюсь, решается простой динамикой по количеству ходов.
Для n = 1 всё понятно. Теперь рассмотрим n > 1. Возьмём первый ход. Если в результате него получили число не меньше чем матожидание для n - 1, то игру выгодно закончить, иначе получаем то самое матожидание для n - 1. Таким образом для каждого n нужно перебрать все возможные результаты первого хода.