The Cookie Game Riley and Morgan play the following cookie game. Given is one set of n red cookies and another set of m green cookies. At every turn, a player must eat two cookies from one set and one cookie from the other set (i. e., either (i) two green cookies and one red cookie, or (ii) two red cookie sand one green cookie). The player who cannot move loses. Assuming Riley will begin the game, which player will win?
Write an efficient dynamic programming algorithm in pseudo-code that decides whether a winning strategy for one of the players exists, give a brief justification of the correctness of your algorithm, and analyze its runtime.
Your algorithm’s input parameters should include n, m∈N0 representing the given numbers of green and red cookies, respectively. As output, the algorithm should state whether Riley or Moran will win, or if there is no winning strategy for either player.