Write the algorithm in a format like this : //Applies dynamic programming to com
ID: 3708603 • Letter: W
Question
Write the algorithm in a format like this :
//Applies dynamic programming to compute the largest number of
//coins a robot can collect on an n × m board by starting at (1, 1)
//and moving right and down from upper left to down right corner
//Input: Matrix C[1..n, 1..m] whose elements are equal to 1 and 0
//for cells with and without a coin, respectively
//Output: Largest number of coins the robot can bring to cell (n, m)
F[1, 1]? C[1, 1]; for j ? 2 to m do F[1, j ]? F[1, j ? 1] + C[1, j ]
for i ? 2 to n do
F[i, 1]? F[i ? 1, 1] + C[i, 1]
for j ? 2 to m do
F[i, j ]? max(F[i ? 1, j ], F[i, j ? 1]) + C[i, j ]
return F[n, m]
Exercise 8.1, problem 7 (a) only 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 from one comer 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. Solve the problem ic programming algorithm a. by a dynam Hint: a chessboard consists of 8x8 squares. You can assume that the chess rook is initially located at the top left corner. You wanted to find the number of the shortest path to move the rook from the top left corner to the bottom right corner. This problem is similar to the path counting problem from the slides. For example, there are 3 different shortest paths to move the rook from (1, 1) to (2, 3) (1, 1) to (1, 2) to (2, 2) to (2, 3) (1, 1) to (2, 1) to (2, 2) to (2, 3)Explanation / Answer
CODING:
#include<bits/stdc++.h>
using namespace std;
int numberOfPaths(int m, int n)
{
// Create a 2D table to store results of subproblems
int count[m][n];
// Count of paths to reach any cell in first column is 1
for (int i = 0; i < m; i++)
count[i][0] = 1;
// Count of paths to reach any cell in first column is 1
for (int j = 0; j < n; j++)
count[0][j] = 1;
// Calculate count of paths for other cells in bottom-up manner using
// the recursive solution
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
count[i][j] = count[i-1][j] + count[i][j-1];
}
return count[m-1][n-1];
}
// Driver program to test above functions
int main()
{
cout << numberOfPaths(8, 8);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.