We are given the board of n×n square tiles (which represents the map of a mountainous terrain), together with the positive cost for any pair of adjacent squares (that represents cost of walking from one square to the other). We would like to traverse the board from left to right. A valid path starts from any square along the left boundary of board, ends at any square along the right boundary of the board, and it can make single moves from one square to an adjacent square (crossing a common edge). The cost of a path is the total cost of the moves between adjacent squares along the path.

Develop a dynamic programming algorithm for finding the minimum cost of a valid path. Define appropriate subproblems, find a recurrence relation for the optimal solution in terms of optimal solutions of subproblems, determine the total number of subproblems, describe a dynamic programming algorithm, and analyze the running time and the space requirement of the algorithm.