Reference no: EM132399198

Coins of various values are placed on the cells of an n × m chess board. Let the upper left corner cell be (1, 1) and the lower right cell be (n, m); cell (i, j) has coins valued at cij . A robot starts at cell (1, 1) and can move only to the right or down on the board. 1. Give a dynamic programming algorithm expressed recursively without memoization to determine the path the robot should follow to maximize the total value of the coins collected as the robot wanders on the board from cell (1, 1) to cell (n, m). Analyze the time required and give corresponding pseudocode. 2. Give the algorithm iteratively with memoization. Analyze the time required and give corresponding pseudocode