Algorithm CS Problem 5 (20 points Recall that in class we defined a lattice path

Question

Algorithm CS

Problem 5 (20 points Recall that in class we defined a lattice path to be a sequence of cells starting with the cell at the lower left corner of a rectangular lattice and ending with the cell at the upper right corner of the lattice, such that given any cell in the sequence, the next cell in the sequence is the adjacent cell either directlyupward from, or directly rightward from, the given cell. Using the dymamic programming algorithm shown in class, find a minimal cost lattice path in the rectangular lattice below. Indicate the path clearly and unambiguously by shading all (and only those squares that are on the path.

Explanation / Answer

code:

int minimum_cost(int cost[r][c], int m, int n)
{
int i, j;

int dp[r][c];
dp[0][0] = cost[0][0];

for (i = 1; i <= m; i++)
dp[i][0] = dp[i-1][0] + cost[i][0];

for (j = 1; j <= n; j++)
dp[0][j] = dp[0][j-1] + cost[0][j];

for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + cost[i][j];

return dp[m][n];
}

you can run the above code on the given matrix

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.