Recall that in class we defined a lattice path to be a sequence of cells startin

Question

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 directly upward from, or directly rightward from, the given cell al-cost Using the dynamic programming algorithm shown in class, find a minim lattice below. Indicate the path clearly and path in the rectangular lattice unambiguously by shading all (and only) those squares that are on the path 3 5 8 3 6 2 66 9 35 4 4 3 4 5

Explanation / Answer

Since we have to reach from lower left corner to upper right corner so we will take a route based on size.

1)first we go from (8,0) i.e 4 to (8,1) i.e '1' instead of (7,0) i.e. 5 as we have to calculate the minimal cost.

So by solving this we will get minimal cost as '61'.

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];
}

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

---

---

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