Data Structures Homework

You are given an (n x n) chessboard and you start at your location of choice (removing confusing statement) on the first row. You have to find the optimal (least-cost) path from the top of the chessboard to the bottom. cost[i][j] represents the cost of moving onto square (i,j) of the chessboard. You move down one row at each step along your path. You may move to the square immediately below you or the squares diagonally below you. That is, when you on square (i,j), you can move down to either (i+1,j), (i+1,j-1), or (i+1,j+1). Your method optimalPath() should use dynamic programming to solve this problem. Define your recurrence equation g(i,j) (which you should represent by an int[][] in your method) to be the cost of the optimal path from the first row to location (i,j). / \ c(i,j) if i = 0 (base case, first row) g(i,j) = < / <figure this part out> if i > 0 (recursive case, depends on row (i-1)) \ PLEASE NOTE: The ArrayLinearList containts the column numbers of the path. For the example above, the resulting ArrayLinearList will contain [2, 1, 1, 2, 3]. Use the following program shell: package dataStructures; class OptimalPath { public static ArrayLinearList optimalPath(int n, int [][]cost) { } // create helper methods if you need } ## Deliverables 1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done. ## Platform Java