Feynman’s Restaurant Problem

Quoting from the Feynman Lectures (Exercises -> Feynman’s restaurant problem):

Given N (dishes on the menu) and M <= N (meals to be eaten at the restaurant), how many new dishes D should you try before switching to ordering the best of them for all the remaining (M–D) meals, in order to maximize the average total ratings of the dishes consumed?

(There are many more great riddles there)