Shortest-path counting A chess rook can move horizontally or vertically to any square in the same row or in the same column of a chessboard. Find the number of shortest paths by which a rook can move form one corner of a chessboard to the diagonally opposite corner. The length of a path is measured by the number of squares it passes through, including the first and the last squares.
a) Formulate a dynamic programming algorithm for solving the above problem. Provide a description in words and pseudocode.
b) State and prove the time and space efficiencies of your algorithm in terms of order notation (e. g., Big-Oh).
c) Solve the problem using elementary combinatorics.

Fill in the following program so that it will correctly calculate the price of the orange juice the user is buying based on the buy one get one sale.#include //main functionint main() { int cartons; float price, total; //prompt user for input information printf("what is the cost of one container of oj in dollars? \n"); scanf(" [ select ] ["%d", "%c", "%f", "%lf"] ", & price); printf("how many containers are you buying? \n"); scanf(" [ select ] ["%d", "%c", "%f", "%lf"] ", & cartons); if ( [ select ] ["cartons / 2", "cartons % 1", "cartons % 2", "cartons % price", "cartons / price", "cartons / total"] [ select ] ["=", "==", "! =", "< =", "> =", "< "] 0) total = [ select ] ["price * cartons", "cartons * price / 2 + price", "(cartons / 2) * price", "cartons / (2.0 * price)", "(cartons / 2.0) * price + price", "((cartons / 2) * price) + price"] ; else total = ((cartons / 2) * price) + price; printf("the total cost is $%.2f.\n", total); return 0; }