Your solution must comply with the following steps:

a) Optimal Substructure and a Recursive Solution

b) Subproblem Overlapping

c) Iterative solution (Write complete algorithm)

d) Analysis of your algorithm

Imagine a climber trying to climb on top of a wall. A wall is constructed out of square blocks of equal size, each of which provides one handhold. Some handholds are more dangerous/complicated than other. From each block the climber can reach three blocks of the row righ above: one right on top, one to the right and one to the left (unless right or left are no available because that is the end of the wall). The goal is to find the least dangerous path from the bottom of the wall to the top, where danger rating (cost) of a path is the sum of danger ratings (costs) of blocks used on that path. We represent this problem as follows. The input is an nm grid, in which each cell has a positive costC(i,j) associated with it. The bottom row is row 1 , the top row is row n. From a cell (i,j) in one step you can reach cells (i+1,j1) (if j>1),(i+1,j) and (i+1,j+1) (if j